Periods of Prime Reciprocals

I've written about the periodic decimal representations of prime number reciprocals before, specifically in a post titled Cyclic Numbers on November 23rd 2019. All prime reciprocals are periodic with periods that are of the form:$$ \frac{p-1}{k} \text{ where } k=1, 2, 3, \dots $$What I'd never considered however, was the relative frequencies of these periods for different values of \(k\). It's not difficult to generate a table (permalink) to show this information. I've considered only primes in the range up to 40,000. See Figure 1.

Figure 1

As can be seen, more than a third of primes have reciprocal periods where \(k=1\). It's only when we reach \(k=31\) that we find no such primes in the range up to 40000. However, if we extend the range up to one million then there are 24 primes \(p\) with a period of \( (p-1)/31 \). These primes are (permalink):

49663, 113647, 129023, 136897, 160829, 163061, 381487, 437287, 462149, 501829, 503131, 591233, 675553, 697687, 699299, 701593, 770909, 791927, 800731, 860623, 863909, 918779, 933349, 969743

It would seem that for any arbitrary \(k\) there will be an infinite series of prime numbers \(p\) have a reciprocal period of \( (p-1)/k \). Sometimes the initial prime number is not all that large. Take \(k=101\) for example. In the range up to one million there are two primes with this property, namely 5051 and 637513. For \( k=197 \) there are three primes: 74861, 818339 and 931811.

For any composite number, the period of its reciprocal is the product of the periods of its prime factors divided by their greatest common divisor. For example:$$ \begin{align} 2077 &= 31 \times 67\\ \text{period} \Big ( \frac{1}{31} \Big ) &= 15 \\ \text{period}  \Big (\frac{1}{67} \Big )&= 33 \\ \text{gcd} (15,33) &=3 \\ \text{period} \Big ( \frac{1}{2077} \Big ) &= \frac{15 \times 33}{3} \\ &= \frac{495}{3} \\ &=165 \end{align}$$What's also of interest is a list of the first primes that are divisible by the various divisors once 1 is subtracted from them. The results are shown in Figure 2 over the range up to 100,000. Notice that there is no result for 41 in this range. Notice that for 2 and 5 a result of 1 is returned. This is because when \(n\) is composite, \(n\).period() returns the value 1 (permalink).

Figure 2

The first prime less 1 that is divisible by 41 is 118901 whose reciprocal has a period of 2900. Thus 41 holds the record for hosting the largest prime minus 1 divisible by numbers between 1 and 50.

Twenty Three

With the 23rd November only two days away, I thought that I'd make a post focused simply on this number 23. I know four people who were born on that day. Firstly, I thought I'd look back over my previous posts and see what references to 23 that I could find:

SUM OF CUBES

Most recently I made a post on Sum of Cubes (October 20th 2020) in which I noted that 23 and 239 are the only integers requiring nine positive cubes for their representation. Only 15 integers require eight cubes: 15, 22, 50, 114, 167, 175, 186, 212, 231, 238, 303, 364, 420, 428, and 454. All other numbers require seven cubes or less. In the case of 23 we have:$$23=1^3+1^3+1^3+1^3+1^3+1^3+1^3+2^3+2^3$$CYCLIC NUMBERS

In a post on Cyclic Numbers (November 23rd 2019), I observed that if the digital period of \(1/p\) where \(p\) is prime is \(p\)−1, then the digits represent a cyclic number. 23 is such a prime because it has a period of 22:$$\frac{1}{23}=\text{ 0.0434782608695652173913 }$$Multiplying 0434782608695652173913 progressively by 1 to 22 yields all possible cyclic permutations of this number:

0434782608695652173913    multiplication by 1

0869565217391304347826    multiplication by 2

1304347826086956521739    multiplication by 3

1739130434782608695652    multiplication by 4

2173913043478260869565    multiplication by 5

2608695652173913043478    multiplication by 6

3043478260869565217391    multiplication by 7

3478260869565217391304    multiplication by 8

3913043478260869565217    multiplication by 9

4347826086956521739130    multiplication by 10

4782608695652173913043    multiplication by 11

5217391304347826086956    multiplication by 12

5652173913043478260869    multiplication by 13

6086956521739130434782    multiplication by 14

6521739130434782608695    multiplication by 15

6956521739130434782608    multiplication by 16

7391304347826086956521    multiplication by 17

7826086956521739130434    multiplication by 18

8260869565217391304347    multiplication by 19

8695652173913043478260    multiplication by 20

9130434782608695652173    multiplication by 21

9565217391304347826086    multiplication by 22

Those two posts were the only two that I could find that were of interest regarding 23. Now let's look elsewhere. 

BIRTHDAY PARADOX

23 pops up in the birthday paradox where, in a group of 23 (or more) randomly chosen people, the probability is more than 50% that some pair of them will have the same birthday. Here is the explanation (source):

With 23 people we have 253 pairs: \(\frac{23 \: 22}{2} = 253\). The chance of two people having different birthdays is:$$1 - \frac{1}{365} = \frac{364}{365} = .997260$$Makes sense, right? When comparing one person's birthday to another, in 364 out of 365 scenarios they won't match. Fine. But making 253 comparisons and having them all be different is like getting heads 253 times in a row -- you had to dodge "tails" each time. Let's get an approximate solution by pretending birthday comparisons are like coin flips.We use exponents to find the probability:$$\big( \frac{364}{365} \big )^{253} = 0.4995$$Our chance of getting a single miss is pretty high (99.7260%), but when you take that chance hundreds of times, the odds of keeping up that streak drop. Fast.

SPECIAL PRIMES

• Sophie-Germain prime: a prime \(p\) is a Sophie-Germain prime if \(2 \times p+1\) is prime. In the case of 23, we have 23 x 2 + 1 = 47, a prime. 
  
  
• Safe prime: a prime \(p\) is a  safe prime if \( \frac{p-1}{2} \) is prime. In the case of 23, we have \( \frac{23-1}{2} =11\) and 11 is prime. 
  
  
• Cunningham chain: 23 is the next to last member of the first Cunningham chain (a sequence of prime numbers) of the first kind to have five terms (2, 5, 11, 23, 47). 
  
  
• Twin prime: 23 is the smallest odd prime that is not a twin prime.
  
  
• Woodell prime: a Woodell number \(W_n\) is any natural number of the form \( W_{n}=n\cdot 2^{n}-1\) for some natural number \(n\). A Woodell prime is simply a Woodell number that is prime. 23 is the second such prime after 7. The progression is 7, 23, 383, 32212254719, ... so they are not that common.
  
  
• Factorial prime: a factorial prime is a prime number that is one less or one more than a factorial (all factorials > 1 are even). 23 = 4!-1 and so it qualifies.
  
  
• Eisenstein prime: this is a little complicated but here is a Wikipedia link for learning more about them. The initial Eisenstein primes are 2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, ...
  
  
• Smarandache–Wellin prime: an integer that in a given base is the concatenation of the first \(n\) prime numbers written in that base is called a Smarandache–Wellin number. If the number is prime, it's called a Smarandache–Wellin prime. The initial such primes are 2, 23 and 2357.
  
  
• Sum of primes: the sum of the first 23 primes is 874, which is divisible by 23, a property shared by few other numbers.
  
  
• Repunit prime: a number whose digits are all 1 is called a repunit and if that number is prime, then it is called a repunit prime. The 23 digit number 11111111111111111111111 is such a prime 

FACTORIALS

The number 23 is the only prime \(p\) such that \(p\)! is \(p\) digits long. 

23! = 25852016738884976640000

In fact 23 is one of only four numbers \(n\) such that \(n\)! is \(n\) digits long. The others are 1, 22, and 24. The number 23! is the smallest pandigital factorial—it contains each digit at least once.

HUMAN GENOME

Human cells (apart from the sex cells) contain 46 chromosomes: 23 from the mother and 23 from the father. The sex cells contain 23 chromosomes. There are$$2^{23}=8,324,608$$ possible combinations of 23 chromosome pairs and thus$$2^{46}=70,368,744,177,664$$ possible combinations when male and female sex cells combine to produce a human.

CHEMISTRY

• Atomic Number: the atomic number is the number of protons in the nucleus and this number uniquely identifies the element. The atomic number of Vanadium is 23 meaning that it has 23 protons in its nucleus. To quote from Wikipedia:

Vanadium is a chemical element with the symbol V and atomic number 23. It is a hard, silvery-grey, malleable transition metal. The elemental metal is rarely found in nature, but once isolated artificially, the formation of an oxide layer (passivation) somewhat stabilizes the free metal against further oxidation.

Figure 1: source

• Atomic Mass Number: the atomic mass number is the total number of protons and neutrons (together known as nucleons) in an atomic nucleus. The stable isotope of Sodium (Na) has an atomic mass number of 23 (11 protons and 12 neutrons). To quote from Wikipedia again:

Sodium is a chemical element with the symbol Na (from Latin "natrium") and atomic number 11. It is a soft, silvery-white, highly reactive metal. Sodium is an alkali metal, being in group 1 of the periodic table. Its only stable isotope is \(^{23}\)Na. The free metal does not occur in nature, and must be prepared from compounds. Sodium is the sixth most abundant element in the Earth's crust and exists in numerous minerals such as feldspars, sodalite, and rock salt (NaCl). Many salts of sodium are highly water-soluble: sodium ions have been leached by the action of water from the Earth's minerals over eons, and thus sodium and chlorine are the most common dissolved elements by weight in the oceans.

ASTRONOMY

To quote from this source:

Today, the Earth's axis is tilted 23.5° from the plane of its orbit around the sun. But this tilt changes. During a cycle that averages about 40,000 years, the tilt of the axis varies between 22.1° and 24.5°.  The average of 22.1° and 24.5° is of course 23.3°.

COSMOLOGY

Not that I believe in dark matter but for those that do, it's postulated that 23% of the Universe consists of it. Here is a graph to convince you it's true!

*********************************************

 There's a lot more that could be said about the number 23 but that will do for now.

Cyclic Numbers

To quote from the source of all wisdom, Wikipedia:

A cyclic number is an integer in which cyclic permutations of the digits are successive integer multiples of the number. The most widely known is the six-digit number 142857, whose first six integer multiples are 

142857 × 1 = 142857

142857 × 2 = 285714

142857 × 3 = 428571

142857 × 4 = 571428

142857 × 5 = 714285

142857 × 6 = 857142

To qualify as a cyclic number, it is required that consecutive multiples be cyclic permutations. Thus, the number 076923 would not be considered a cyclic number, because even though all cyclic permutations are multiples, they are not consecutive integer multiples: 

076923 × 1 = 076923

076923 × 3 = 230769

076923 × 4 = 307692

076923 × 9 = 692307

076923 × 10 = 769230

076923 × 12 = 923076 

If leading zeros are not permitted on numerals, then 142857 is the only cyclic number in decimal, due to the necessary structure given in the next section. Allowing leading zeros, the sequence of cyclic numbers begins: 

(\(10^6-1\)) ÷ 7 = 142857 (6 digits)

(\(10^{16}-1\)) ÷ 17 = 0588235294117647 (16 digits)

(\(10^{18}-1\)) ÷ 19 = 052631578947368421 (18 digits)

(\(10^{22}-1\)) ÷ 23 = 0434782608695652173913 (22 digits)

(\(10^{28}-1\)) ÷ 29 = 0344827586206896551724137931 (28 digits)

However, it was in the realm of repeating decimals that I first encountered cyclic numbers. Specifically, I was looking at OEIS entries for 25801, a number representing my diurnal age at the time of composing this blog post, and I came across this entry:

A056215: primes \(p\) for which the period of reciprocal = \( \displaystyle \frac{p-1}{10} \) 

281, 521, 1031, 1951, 2281, 2311, 2591, 3671, 5471, 5711, 6791, 7481, 8111, 8681, 8761, 9281, 9551, 10601, 11321, 12401, 13151, 13591, 14831, 14951, 15671, 16111, 16361, 18671, 21191, 21521, 21881, 24281, 24551, 25391, 25801, ...

Sure enough, when I checked on SageMathCell, the period of this reciprocal is indeed 2580 (see Figure 1):

Figure 1: permalink

After 2580 decimal places, the digits do repeat (shown in red):

0.0000387581876671446843145614511065462578969807371807294290918956629588000465098252005736211774737413278555094763768846168753149102747955505600558117902406883454129684895934266113716522615402503778923297546606720669741482888260144955621875121119336459827138483004534707957055928064803689779465912173946746250145343203751792566179605441649548467113677764427735359094608736095500174411844502151079415526529979458160536413317313282430913530483314600209294213402581295298631835975349792643695980775938917096236579977520251153056083097554358358203170419751172435176931126700515483895973024301383667299717065230029843804503701406922212317352040618580675167629161660400759660478276035812565404441688306654780822448742296810201154993992480911592573931242975078485330025967985736986938490756172241385992790977093911088717491570094182396031161582884384326188907406689663191349172512693306460989884113018875237393899461261191426688888027595829619007015231967753187860935622650284872679353513429712026665633114995542808418278361303825433122747180341847215224216115654431998759737994651370101934033564590519747296616410216658269059338785318398511685593581644122320840277508623696755939692259989922871206542382078214022712297972946785008333010348436107127630711987907445447850858493856827254757567536142009999612418123328553156854385488934537421030192628192705709081043370411999534901747994263788225262586721444905236231153831246850897252044494399441882097593116545870315104065733886283477384597496221076702453393279330258517111739855044378124878880663540172861516995465292042944071935196310220534087826053253749854656796248207433820394558350451532886322235572264640905391263904499825588155497848920584473470020541839463586682686717569086469516685399790705786597418704701368164024650207356304019224061082903763420022479748846943916902445641641796829580248827564823068873299484516104026975698616332700282934769970156195496298593077787682647959381419324832370838339599240339521723964187434595558311693345219177551257703189798845006007519088407426068757024921514669974032014263013061509243827758614007209022906088911282508429905817603968838417115615673811092593310336808650827487306693539010115886981124762606100538738808573311111972404170380992984768032246812139064377349715127320646486570287973334366885004457191581721638696174566877252819658152784775783884345568001240262005348629898065966435409480252703383589783341730940661214681601488314406418355877679159722491376303244060307740010077128793457617921785977287702027053214991666989651563892872369288012092554552149141506143172745242432463857990000387581876 ...

Now the Wikipedia article states that:

If the digital period of \( \displaystyle \frac{1}{p}\) where \(p\) is prime is \(p − 1\), then the digits represent a cyclic number.

That clearly isn't the case with 25801. However, in the comments to the OEIS entry, it states:

Cyclic numbers of the tenth degree (or tenth order): the reciprocals of these numbers belong to one of ten different cycles. Each cycle has the following number of digits: 

\( \displaystyle \frac{number- 1}{10} \)

So 25801 is not a prime that produces a cyclic number. The nearest smaller prime that does this is 25793 and the nearest larger prime that does this is 25847. The primes that produce cyclic numbers are known as reptend primes. In this regard, Wikipedia states that:

Cyclic numbers are related to the recurring digital representations of unit fractions. A cyclic number of length \(L\) is the digital representation of: 

\(\displaystyle \frac{1}{L + 1} \)

Conversely, if the digital period of \( \displaystyle \frac{1} {p} \), where \(p \) is prime, is \(p-1\), then the digits represent a cyclic number. 

For example: 

\( \displaystyle \frac{1}{7}\) = 0.142857 142857…. 

Multiples of these fractions exhibit cyclic permutation: 

\( \displaystyle \frac{1}{7}\) = 0.142857 142857…

\( \displaystyle \frac{2}{7}\) = 0.285714 285714…

\( \displaystyle \frac{3}{7}\) = 0.428571 428571…

\( \displaystyle \frac{4}{7}\) = 0.571428 571428…

\( \displaystyle \frac{5}{7}\) = 0.714285 714285…

\( \displaystyle \frac{6}{7}\) = 0.857142 857142….

Checking reveals the nearby primes to 25801, namely 25793 and 25847, do have periods of 25792 and 25846 respectively. These periods are decimal maximal periods, the maximum length that a repeating decimal of this form can have. See Figure 2.

Figure 2: permalink

I accidentally typed in 258487 when checking and it turns out that the period of its reciprocal is 258486 and so it is a reptend prime as well. However, as stated earlier, 25801 is not a reptend but is regarded as a cyclic number of the tenth degree or tenth order. The terminology can get confusing. Let's start again with the reptend primes. These are also referred to as long period primes and form part of a categorisation involving different values of \(k\):$$\text{Primes }p \text{ such that the period of }\displaystyle \frac{1}{p} \text{ is } \displaystyle \frac{p-1}{k} \text{ where }k=1,2,3,4, ...$$The sequences generated by applying these formulae are listed in the cross references for the original OEIS A056215 entry:

A006883, A097443, A055628, A056157, A056210, A056211, A056212, A056213, A056214, A056215, A056216, A056217, A098680, which are sequences of primes \(p \) where the period of the reciprocal is \( \displaystyle \frac{p-1}{k}\) for \(k=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13\) respectively.

So I think my confusion has been clarified. It is only when \(k=1\) that the reciprocal produces a cyclic number. The Wikipedia goes on to state that:

From the relation to unit fractions, it can be shown that cyclic numbers are of the form of the Fermat quotient:$$ \displaystyle \frac {b^ {\,p-1}-1}{p}$$ where \(b\) is the number base (10 for decimal), and \(p\) is a prime that does not divide \(b\). Primes \(p\) that give cyclic numbers in base \(b \) are called full reptend primes or long primes in base \(b\). 

For example, the case \(b = 10\), \(p = 7\) gives the cyclic number 142857, and the case \(b = 12\), \(p = 5\) gives the cyclic number 2497. 

Not all values of \(p\) will yield a cyclic number using this formula; for example, the case \(b = 10\), \(p = 13\) gives 076923076923, and the case \(b = 12\), \(p = 19\) gives 076B45076B45076B45. These failed cases will always contain a repetition of digits (possibly several).

I won't go into the other number bases here and I haven't followed up on the link to Fermat primes. Here is a Numberphile YouTube video about cyclic numbers:

The video highlights how some of the formulae arise. For example:$$ \begin{align}\frac{1}{7} &=0.142857142857142857142857 ... \\
10^6 \times \frac{1}{7} &=142857.142857142857142857142857 ... \\
\frac{10^6}{7}-142857 &=0.142857142857142857142857 ...\\
\frac{10^6}{7}-142857 &=\frac{1}{7} \\
142857&=\frac{10^6-1}{7}\\
\end{align}$$Interestingly, there is even a reference to Gurdjieff in this video because the number 142857 features in his enneagram as shown in Figure 3.

Figure 3: 

As explained in Wikipedia:

The Fourth Way enneagram is a figure published in 1949 in In Search of the Miraculous by P.D. Ouspensky, and an integral part of the Fourth Way esoteric system associated with George Gurdjieff. The term "enneagram" derives from two Greek words, ennea (nine) and gramma (something written or drawn).

I won't further into that here as this blog focuses purely on Mathematics but I may follow up on it in my other blogs.

on February 27th 2021

Euler's Totient Function

From Wikipedia:

Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function.

Today I turned 25545 days old and one of the points of interest about this number is that it forms a pair with 25546, both having the property that their totient values are the same (12480). The first member of the pairs of numbers with this property up to and including 25545 is given by OEIS A001274: numbers \(n\) such that \( \phi(n) = \phi(n+1) \):

1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545

Note that for all prime numbers \(p\), \( \phi(p)=p-1 \). These totient values (totatives) represent the maximum possible for numbers up to \(p\) and their points lie on the maximal line as shown in Figure 1:

Figure 1: generated using SageMathCell using
plot(lambda x:euler_phi(int(x)), (x,1,100))

From Figure 1 it can be seen that the totient values (totatives) for 1 and 2, 3 and 4, 15 and 16 are the same. Note that 5186 and 5187 themselves form a pair, meaning that the totient values of 5186, 5187 and 5188 are the same (2592). This is the only triplet that occurs for numbers up to \( 10^{13} \).

Euler's totient function is a multiplicative function, meaning that if two numbers \(m\) and \(n\) are relatively prime, then \( \phi(m \times n) = \phi(m) \times \phi(n) \). This is important in developing Euler's product formula along with the fact that: $$\phi(p^k)=p^{k-1} \bigg (1-\frac{1}{p} \bigg )$$The product formula is: $$\phi(n)=n \prod_{p|n} \bigg (1-\frac{1}{p} \bigg )$$Applying this to today's number 25545=3 * 5 * 13 * 131, we note that:$$ \phi(25545) = 25545\bigg (1-\frac{1}{3} \bigg ) \bigg (1-\frac{1}{5} \bigg ) \bigg (1-\frac{1}{13} \bigg ) \bigg (1-\frac{1}{131} \bigg )=12480$$