Showing posts with label reciprocal. Show all posts
Showing posts with label reciprocal. Show all posts

Friday, 17 July 2026

Artin's Constant

My diurnal age today is 28229, a prime, with a reciprocal that has a period of 28228. It is thus one of those primes \(p\) with a period that is given by \( \dfrac{1}{p-1}\).

I got to wondering what proportion of primes have reciprocals that are one less than the prime itself. I asked Gemini. It's response follows and comprises the rest of this post.

Approximately 37.3956% of all prime numbers have reciprocals with a repeating decimal period of maximum length, \(p - 1\). In number theory, primes with this property are known as full reptend primes (or long primes) in base 10.

The Number Theory Behind Maximal Periods

The number of digits in the repeating period of the reciprocal \(1/p\) is determined by the multiplicative order of \(10\) modulo \(p\), denoted as \(\text{ord}_p(10)\).

By Fermat's Little Theorem, for any prime \(p \neq 2, 5\), the period length \(k\) is the smallest positive integer such that:

\[10^k \equiv 1 \pmod{p}\]

Since the multiplicative group \((\mathbb{Z}/p\mathbb{Z})^\times\) has order \(\phi(p) = p - 1\), Lagrange's theorem dictates that the period length \(k\) must always divide \(p - 1\).

For the period to achieve the absolute maximum length of \(p - 1\), the integer \(10\) must be a primitive root modulo \(p\). When \(10\) is a primitive root, the successive powers of \(10 \pmod{p}\) cycle through every possible non-zero remainder from \(1\) to \(p - 1\) before repeating, generating a cyclic period of length \(p - 1\).


Artin's Constant and Asymptotic Density

The exact asymptotic density of primes for which a given integer is a primitive root is governed by Artin's conjecture on primitive roots.

Because the base \(a = 10\) is neither a perfect square nor \(-1\), Artin's conjecture predicts that the proportion of full reptend primes among all primes up to \(N\) converges to a universal mathematical constant as \(N \to \infty\). This value is known as Artin's constant (\(C_{\text{Artin}}\)), defined by the infinite product over all prime numbers \(q\):

\[C_{\text{Artin}} = \prod_{q \text{ prime}} \left(1 - \frac{1}{q(q-1)}\right) \approx 0.3739558136\dots\]

While Emil Artin's conjecture remains unconditionally unproven for specific bases like 10, Christopher Hooley proved in 1967 that the asymptotic density is exactly \(C_{\text{Artin}}\) under the assumption of the Generalized Riemann Hypothesis (GRH). Extensive computational verification confirms that the distribution stabilizes at this ~37.3956% threshold (cataloged as decimal expansion A005596 in the OEIS).


Period Lengths of Small Primes

Comparing the first few primes highlights how the multiplicative order behaves when \(10\) is (and is not) a primitive root:

Prime (\(p\)) Reciprocal (\(1/p\)) Period Length (\(\text{ord}_p(10)\)) Full Reptend? (\(k = p - 1\))
3 \(0.\overline{3}\) \(1\) No
7 \(0.\overline{142857}\) \(6\) Yes
11 \(0.\overline{09}\) \(2\) No
13 \(0.\overline{076923}\) \(6\) No
17 \(0.\overline{0588235294117647}\) \(16\) Yes
19 \(0.\overline{052631578947368421}\) \(18\) Yes
23 \(0.\overline{0434782608695652173913}\) \(22\) Yes

The sequence of base-10 full reptend primes continues: \(7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, \dots\) (OEIS sequence A001122). Noticeably, primes like \(13\) (where \(10^6 \equiv 1 \pmod{13}\)) and \(37\) (where \(10^3 \equiv 1 \pmod{37}\)) fall into sub-cyclic periods because their multiplicative orders are proper divisors of \(p - 1\).

Friday, 18 October 2024

An Interesting Prime

Being born on the 3rd April 1949, my date of birth is often represented as 3 - 4 - 49. These numbers when concatenated form the prime number 3449. I was reminded of this number because of the factorisation of the number associated with my diurnal age today, 27592.$$27592 = 2^3 \times 3449 = 8 \times 3449$$So today my life can be divided into exactly eight equal parts, each of them 3449 days long which is about 9.44 years. The previous multiple$$7 \times 3449 = 24143$$occurred on May 10th 2015 when I was still working at the Shanghai Singapore International School. The next multiple$$9 \times 3449 = 31041$$ will fall on March 29th 2034, shortly before my 84th birthday (if I make it that far).

3449 forms the initial prime of a Cunningham chain of the first type with length exactly 3 and so: $$ 3449 \rightarrow 2 \times 3449 + 1 = 6889 \text{ (prime)} \\ 6889 \rightarrow 2 \times 6889 +1 = 13799 \text{ (prime)}$$Primes with this property form OEIS A059762. Another prime-related property of 3449 qualifies it for membership in OEIS A088483:


A088483
: primes \( \textit{p} \) such that \(p^2+p-1\) and \(p^2+p+1\) are twin primes.

For 3449, the twin primes are \(11899049\) and \(11899051\). 

3449 is also a home prime with a homeliness of 3 because:$$ \begin{align} 611 &= 13 \times 47 \rightarrow 1347\\ 1347 &= 3 \times 449 \rightarrow 3449 \end{align}$$Not all primes are home primes of course. Take 613 as an example of a prime that is not a home prime because it cannot be formed by the concatenation of the prime factors of any number (the prime factors need to be concatenated in ascending order).

3449 is also a member of OEIS A153116:


A153116
: primes \(p\) such that \(p^2 +12\) and \(p^2-12\) are also primes.

Here the two primes are \(11895589\) and \(11895613\). Additionally:$$ \text{period of}\frac{1}{3449}=\frac{3449-1}{8} = 431$$This property qualifies 3449 for membership of OEIS A056213:


A056213: primes \(p\) for which the period of reciprocal = \(\dfrac{p-1}{8}\).

3449 is a Sophie Germain prime because:$$2 \times 3449+1=6899 \text{ is prime}$$3449 also features in so-called "Golden Semiprimes" and this qualifies it for membership in OEIS A108544:


A108544
: primes that are factors of distinct golden semiprimes (A108540).


I posted about these types of semiprimes in Semiprime Factor Ratios way back on the 26th August 2016. In that post I said that:

A golden semiprime is a number that factors to:
  • \(p \times q\) where \(p\) and \(q\) are prime
  • \( | \,p \, \phi - q \,| <1\) where \(\phi=\dfrac{\sqrt{5}+1}{2} \)
In the case of 3449, it is the \(q\) and \(p=2131\) and the golden semiprime is:$$7349819=2131 \times 3449$$The OEIS mentions 314 sequences in which 3449 makes an appearance and I've only dealt with a few of them here. However, I see 3449 as an important number in my life and didn't want its current occurrence to pass unnoticed.

Wednesday, 29 May 2024

The Harmonic Mean

I keep coming across a certain type of problem and so I gave Google's Gemini the opportunity to explain the solution. What follows is our interaction.

Here is a problem. 

A worker A can complete a task in 50 minutes and another worker B can complete the same task in 40 minutes. If they work together, how long will it take them to complete the task. 

Can you explain how the answer is reached?

Absolutely! Here's how we can find how long it takes workers A and B to complete the task together:

1. Rate of Each Worker:

Instead of focusing on the complete time each worker takes, we can think about their rates of completing the task.

Worker A's rate: We can say A completes 1/50th of the task every minute (since they take 50 minutes to do the whole thing).

Worker B's rate: Similarly, B completes 1/40th of the task every minute.

2. Combined Rate:

When A and B work together, they essentially combine their rates. So, their combined rate is the sum of their individual rates:

Combined Rate = Rate of A + Rate of B

Combined Rate = \( \dfrac{1}{50} + \dfrac{1}{40} \)

3. Finding the Combined Time:

Imagine the combined rate represents how much of the task they complete every minute when working together. Since they combine their efforts, they'll finish the entire task (which is 1 unit of work) when the combined rate reaches 1.

Therefore:

Time taken to complete the task together:

$$ \begin{align} x &= \frac{\text{Total work (1)}}{\text{ Combined Rate} }\\ &= \frac{1}{ \dfrac{1}{50} + \dfrac{1}{40}} \end{align}$$

4. Simplifying the Math:

To simplify the above equation, we can find a common denominator for the fractions (which is the least common multiple of 50 and 40, which is 200):

$$ \begin{align} x &= \frac{1}{ \dfrac{1}{50} + \dfrac{1}{40}} \\ &= \frac{1}{\dfrac{9}{200}} \end{align}$$

5. Final Answer:

Inverting the fraction gives us the total time: $$ \begin{align} x &= \frac{200}{9} \\ &= 22 \frac{2}{9} \text{ minutes (approximately)} \end{align} $$

Explanation:

By combining their rates, we essentially calculate how much faster they complete the task together compared to working individually. This combined rate helps us determine the total time it takes for them to finish the entire task.

Has this got anything to do with means, such as the harmonic mean or the geometric mean?

You've got a good eye! In this specific case, the method we used to find the time to complete the task together is closely related to the harmonic mean.

Here's why:

The harmonic mean is ideal for finding the average rate when rates are involved.

In this problem, we weren't finding the average time to complete the task, but the average rate at which they work together (which is the reciprocal of the average time).

Mathematically, the harmonic mean of two numbers a and b is:

harmonic mean = \( \dfrac{2 a  b}{  a + b} \)

While we didn't use this exact formula, the underlying principle is the same. We took the individual rates (1/50 and 1/40), essentially representing how much of the task they complete per minute, and combined them proportionally using a common denominator. This combined rate represents the average rate at which they work together, which is what the harmonic mean helps us find.

The geometric mean, on the other hand, wouldn't be applicable here. It's used for finding the average of multiplied quantities, which isn't the case in this scenario.

Monday, 1 January 2024

Unitary Harmonic Numbers

As I'm creating this post it is the first day of 2024 but on the last day of 2023, I came across the term Unitary Harmonic Number for the first time. This is not surprising as they are quite rare. The initial numbers, up to 40000, are 1, 6, 45, 60, 90, 420, 630, 1512, 3780, 5460, 7560, 8190, 9100, 15925, 16632, 27300 and 31500. Yesterday, my diurnal age was 27300 which is why the term came to my attention.

A unitary harmonic number is defined as a number whose unitary divisors have a harmonic mean that is an integer. This is clearly not often the case. Let's take the number 12. It has divisors of 1, 2, 3, 4, 6 and 12. Of these, only 1, 3, 4 and 12 are unitary divisors. Let's recall that a unitary divisor of a number is a divisor such that, when divided into the number, the result is a number that has no factors in common with the divisor. For example, 2 divides into 12 to give 6 but 6 and 2 have 2 as a common factor and so 2 is not a unitary divisor. 3 however divides into 12 to give 4. 3 and 4 have no common factor and so 3 is a unitary divisor. 

Let's look at 27300. It has the following divisors:

1, 2, 3, 4, 5, 6, 7, 10, 12, 13, 14, 15, 20, 21, 25, 26, 28, 30, 35, 39, 42, 50, 52, 60, 65, 70, 75, 78, 84, 91, 100, 105, 130, 140, 150, 156, 175, 182, 195, 210, 260, 273, 300, 325, 350, 364, 390, 420, 455, 525, 546, 650, 700, 780, 910, 975, 1050, 1092, 1300, 1365, 1820, 1950, 2100, 2275, 2730, 3900, 4550, 5460, 6825, 9100, 13650, 27300

There are 32 unitary divisors of 27300 and they are:

1, 3, 4, 7, 12, 13, 21, 25, 28, 39, 52, 75, 84, 91, 100, 156, 175, 273, 300, 325, 364, 525, 700, 975, 1092, 1300, 2100, 2275, 3900, 6825, 9100, 27300

The harmonic mean of a set of numbers is defined as the reciprocal of the average of the reciprocals of the numbers. The sum of the 32 reciprocals of the unitary divisors is 32/15 and thus their average is 1/15 which becomes 15 when we consider the reciprocal. Numbers like 27300 comprise OEIS A006086 (permalink):


 A006086

Unitary harmonic numbers (those for which the unitary harmonic mean is an integer).



The next unitary harmonic number will occur when I'm 31500 days old which I may or may not be around to celebrate. For posts relating to the harmonic mean see Reciprocals of Primes and Root-Mean-Square And Other Means.

Monday, 8 May 2023

Brazilian Primes

There's only one reference that I've made to Brazilian primes in this blog and that was in a post titled Fermat Primes and Brazilian Numbers on February 26th 2018 which is now over five years ago. I was reminded of them once again when a number associated with my diurnal age, 27061, was identified as a Brazilian prime. I wrote the following about Brazilian numbers in that earlier post:

These numbers are listed in OEIS A125134 and defined as:

Numbers \( n \) such that there is a natural number \( b \) with \( 1 < b < n-1 \) such that the representation of \( n \) in base \( b \) has all equal digits.

All even numbers \( \geq \) 8 are Brazilian numbers because: $$ \begin{align} 2p&=2(p-1)+2 \\&= 22 \end{align}$$in base \(p-1\) if \(p-1>2 \) and that is true if \(p \geq 4 \). 

The odd Brazilian numbers are listed in OEIS A257521 and are fairly common, with some being prime numbers:

7, 13, 15, 21, 27, 31, 33, 35, 39, 43, 45, 51, 55, 57, 63, 65, 69, 73, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 127, 129, 133, 135, 141, 143, 145, 147, 153, 155, 157, 159, 161, 165, 171, 175, 177, 183, 185, 187, 189, 195, ...

As an example, take 27 in the above sequence which can be expressed as \(33_8 \). As for the even numbers, take a number like 28. It can be written as 2 x (14-1) + 2 and thus can be represented as \(22_{13} \).

Brazilian primes are simply Brazilian numbers that are prime. These constitute OEIS A085104:


 A085104

Primes of the form \(1 + n + n^2 + n^3 + ... + n^k \) where \(n > 1\) and \( k > 1\).


For example, in the case of 27061 we have: $$ \begin{align} 27061& = 1+164+164^2 \\ &= 164^2+164+1\\&=111_{164} \end{align}$$These primes can be generated using this permalink. The initial members of the sequence are:

7, 13, 31, 31, 43, 73, 127, 157, 211, 241, 307, 421, 463, 601, 757, 1093, 1123, 1483, 1723, 2551, 2801, 2971, 3307, 3541, 3907, 4423, 4831, 5113, 5701, 6007, 6163, 6481, 8011, 8191, 8191, 9901, 10303, 11131, 12211, 12433, 13807, 14281, 17293, 19183, 19531, 20023, 20593, 21757, 22621, 22651, 23563, 24181, 26083, 26407, 27061, 28057, 28393, 30103, 30941, 31153, 35533, 35911, 37057, 37831, 41413, 42643, 43891, 46441, 47743, 53593, 55933, 55987, 60271, 60763, 71023, 74257, 77563, 78121, 82657, 83233, 84391, 86143, 88741, 95791, 98911

The OEIS comments to this sequence are informative:

The number of terms \(k+1\) is always an odd prime, but this is not enough to guarantee a prime, for example 111 = 1 + 10 + 100 = 3 x 37.

The inverses of the Brazilian primes form a convergent series; the sum is slightly larger than 0.33.

It is not known whether there are infinitely many Brazilian primes. 

Brazilian primes can be written in the form:

$$ \dfrac{(n^p - 1)}{(n - 1}\\ \text{ where } p \text{ is an odd prime and } n > 1$$

The number of terms less than \(10^n\) are 1, 5, 14, 34, 83, 205, 542, 1445, 3880, 10831, 30699, 88285, ...

Brazilian primes fall into two classes:

  • when \(n\) is prime, we get sequence OEIS A023195 except 3 which is not Brazilian,
  • when \(n\) is composite, we get sequence OEIS A285017.

The conjecture that "No Sophie Germain prime is Brazilian (prime)"  is false because:$$ \begin{align} a(856) &= 28792661\\ &= 1 + 73 + 73^2 + 73^3 + 73^4 \\&= (11111)_{73} \end{align} $$and 28792661 is the 141385-th Sophie Germain prime.