More on Anti-divisors

Back in February of 2016, I made a post about anti-divisors but I've posted nothing about them since. However, I was reminded of them once again because today I turned 26264 days old and one of the properties of this number is that it's a member of OEIS:

A109351

Numbers whose anti-divisors sum to a perfect cube.

The anti-divisors of 26264 are 3, 16, 112, 784, 1072, 7504 and 17509. My original post explains how anti-divisors are determined so I won't repeat all of that here but essentially:

• if the anti-divisor \(k\) of the number \(n\) is even then \( n \equiv \displaystyle \frac{k}{2} \mod{k} \)
• if the anti-divisor \(k\) of the number \(n\) is odd then \( n \equiv \displaystyle \frac{k+1}{2} \mod{k} \text{ or } \displaystyle \frac{k-1}{2} \mod{k} \)

In the case of 26264 and its anti-divisors, we find that:

• \( 26264 \equiv 2 \mod{3} \text{ and  } 2=\displaystyle \frac{3+1}{2}\)
• \( 26264 \equiv 8 \mod{16} \text{  and  } 8=\displaystyle \frac{16}{2}\)
• \( 26264 \equiv 56 \mod{112} \text{  and  } 56=\displaystyle \frac{112}{2} \)
• \( 26264 \equiv 397 \mod{784} \text{  and  } 397=\displaystyle \frac{784}{2}\)
• \( 26264 \equiv 536 \mod{1072} \text{  and  } 536=\displaystyle \frac{1072}{2}\)
• \( 26264 \equiv  3752 \mod{7504} \text{  and  } 3752=\displaystyle \frac{7504}{2}\)
• \( 26264 \equiv  8755 \mod{17509} \text{  and  } 8755= \displaystyle \frac{17509+1}{2}\)

There are lots of interesting facts about anti-divisors listed on this source:

• Every integer \(n\) has a largest anti-divisor, and this is at approximately at 2/3rds of \(n\).  

• Every number has a unique set of anti-divisors. 

• Anti-primes (integers with only one anti-divisor) are rare and include 3, 4, 6, 96 and 393216. These numbers form OEIS A066466.

• Anti-perfect numbers are integers such that the sum of its anti-divisors equals the original integers. Figure 1 shows a list of the initial members. 

Figure 1

 The anti-perfect numbers form OEIS A073930:

A073930

Numbers \(n\) such that \(n\) = sum of the anti-divisors of \(n\).

5, 8, 41, 56, 946, 5186, 6874, 8104, 17386, 27024, 84026, 167786, 2667584, 4921776, 27914146, 505235234, 3238952914, 73600829714, 455879783074, 528080296234, 673223621664, 4054397778846, 4437083907194, 4869434608274, 6904301600914, 7738291969456

This extends the list of such numbers shown in Figure 1. 

• Anti-multiperfect numbers are integers that equals some product of the sum of its anti-divisors. See Figure 2.

Figure 2

• An anti-amicable pair of numbers are two or more numbers such that the sum of the anti-divisors of one equals another, and then the sum of the anti-divisors of this number equal the original number. The idea here can be extended to form chains of anti-amicable numbers - these can be referred to as anti-sociable numbers. See Figure 3.

Figure 4

• Some numbers have a large number of anti-divisors. For example, 2139637 has 155 anti-divisors:

2, 3, 5, 7, 9, 11, 13, 15, 19, 21, 25, 33, 34, 35, 39, 45, 53, 55, 57, 63, 65, 75, 77, 86, 91, 95, 99, 105, 117, 133, 143, 165, 171, 175, 195, 209, 225, 231, 247, 263, 273, 275, 285, 307, 315, 325, 385, 399, 429, 455, 475, 495, 525, 585, 627, 665, 693, 715, 741, 819, 825, 855, 975, 1001, 1045, 1155, 1197, 1235, 1287, 1365, 1425, 1462, 1463, 1575, 1729, 1881, 1925, 1995, 2145, 2223, 2275, 2475, 2717, 2925, 3003, 3135, 3325, 3465, 3575, 3705, 4095, 4275, 4389, 5005, 5187, 5225, 5775, 5854, 5985, 6175, 6435, 6825, 7315, 8151, 8645, 9009, 9405, 9975, 10725, 11115, 13167, 13585, 13939, 15015, 15561, 15675, 16271, 17325, 18525, 19019, 20475, 21945, 24453, 25025, 25935, 29925, 32175, 36575, 40755, 43225, 45045, 47025, 55575, 57057, 65835, 67925, 75075, 77805, 80741, 95095, 99518, 109725, 122265, 129675, 171171, 203775, 225225, 251722, 285285, 329175, 389025, 475475, 611325, 855855, 1426425

Figure 5 shows a table of the first few maximally anti-divisible (MAD) natural numbers:

Figure 5

As can be seen the list in Figure 5 is missing some NADs (Number of Anti-Divisors). The full list can be found is OEIS 

 

A066464

Least number \(k\) such that \(k\) has \(n\) anti-divisors.

 The full list runs like this where first column is \(n\) and second column is \(k\).

0         1

1         3

2         5

3         7

4         13

5         17

6         32

7         38

8         85

9         67

10     162

11     137

12     338

13     203

14     760

15     247

16     1225

17     472

18     578

19     682

20     1012

21     787

22     9112

23     1463

24     2048

25     2047

26     2888

27     2363

28     5513

29     3465

30     5512

31     6682

32     8978

33     5197

34     17672

35     5198

36     71442

37     9653

38     29768

39     8662

40     40898

41     13513

42     81608

43     15593

44     131072

45     35437

46     49612

47     26163

48     74498

49     22522

50     37538

• A MAD run is a series of MAD numbers such that the NAD (Number of Anti-Divisors) value increases by 2. Figure 5 shows that there is an opening MAD run from 1 to 29 and after this, they become rarer, and almost disappear. Notably 293,295,297,299,301 forms a MAD run of 5.
  
  
• MAD twins are consecutive MAD numbers. Figure 6 shows these:

Figure 6

Most of this content has come from an additional link to the Internet Archive and forms a sort of parallel anti-matter universe to the one that most people are familiar. There are many interesting sequences in the OEIS, some of which are listed above. Here are some more:

A178029

Numbers whose sum of divisors equals the sum of their anti-divisors.

Initial members of this sequence are:

11, 22, 33, 65, 82, 117, 218, 483, 508, 537, 6430, 21541, 117818, 3589646, 7231219, 8515767, 13050345, 47245905, 50414595, 104335023, 217728002, 1217532421, 1573368218, 1875543429, 2269058065, 11902221245, 12196454655, 12658724029

For example, 21541 has anti-divisors 2, 3, 9, 26, 67, 643, 3314, 4787 and 14361 that sum to 23212 and divisors 1, 13, 1657 and 21541 that also sum to 23212.

A241557

Numbers \(k\) that do not have prime anti-divisors.

Initial members of this sequence are:

1, 2, 6, 30, 36, 54, 90, 96, 114, 120, 156, 174, 210, 216, 300, 330, 414, 510, 516, 546, 576, 660, 714, 726, 744, 804, 810, 834, 894, 936, 966, 1014, 1044, 1056, 1134, 1170, 1296, 1344, 1356, 1500, 1560, 1584, 1626, 1650, 1680, 1686, 1734, 1764, 1770, 1836, 1884, 1926, 2010, 2046, 2064

For example, 2064 has anti-divisors 32, 96 and 1376, none of which are prime.

A073956

Palindromes whose sum of anti-divisors is palindromic.

Initial members of this sequence are:

1, 2, 3, 4, 5, 6, 8, 9, 242, 252, 323, 434, 727, 4774, 32223, 42024, 43234, 46864, 64946, 70607, 4855584, 4942494, 6125216, 6265626, 149939941, 188737881, 241383142, 389181983, 470212074, 27685458672, 42685658624, 45625352654, 61039793016

For example, the palindrome 46864 has anti-divisors 3, 19, 32, 157, 199, 471, 597, 928, 3232, 4933 and 31243 that sum to 41814 which is also a palindrome.

A192282

Numbers \(n\) such that \(n\) and \(n+1\) have same sum of anti-divisors.

Initial members of this sequence are:

1, 8, 17, 120, 717, 729, 957, 8097, 10785, 12057, 35817, 44817, 52863, 58677, 59757, 76759, 95397, 102957, 114117, 119337, 182157, 206097, 215997, 230037, 253977, 263877, 269277, 271797, 295377, 321417, 402657, 435477, 483117, 485637, 510837, 586797, 589317 

For example, 35817 has anti-divisors 2, 5, 6, 14327 and 23878 that sum to 38218. The next number 35818 has anti-divisors 3, 4, 5, 14327 and 23879 that also sum to 38218.

A242965

Numbers whose anti-divisors are all primes.

Initial members of this sequence are:

3, 4, 5, 7, 8, 11, 16, 17, 19, 29, 43, 47, 61, 64, 71, 79, 89, 101, 107, 109, 151, 191, 197, 223, 251, 271, 317, 349, 359, 421, 439, 461, 521, 569, 601, 631, 659, 673, 691, 701, 719, 811, 821, 881, 911, 919, 947, 971, 991, 1009, 1024, 1051, 1091, 1109, 1153 

For example, 1153 has anti-divisors 2, 3, 5, 461 and 769, all of which are prime.

That's probably enough anti-divisor related sequences for this post but let's be clear, with the exception of 1 and 2, all integers have:

• at least two divisors (themselves and 1) e.g. 11 has divisors 11 and 1
• at least one non-divisor e.g. 11 has non-divisors of 2, 3, 4, 5, 6, 7, 8, 9 and 10
• at least one non-divisor that is an anti-divisor e.g. 11 has anti-divisors of 2, 3 and 7.

Anti-divisors can be quickly found in SageMath (or Python) using the following code (input is in blue and output is in red, see Figure 7 for screenshot):

from sympy.ntheory.factor_ import antidivisors

n=1134

print(antidivisors(int(n)))

[4, 12, 28, 36, 84, 108, 252, 324, 756] 

Figure 7: permalink

26262: A Special Palindrome

Indeed, "There are things that drift away, like our endless numbered days" and 26262 is one of them. Today I turned 26262 days old and this number should pass away perhaps only after it has received its due attention. 

So what makes this particular palindrome special? Well, to begin with, it's sandwiched between two primes and that doesn't happen often as OEIS A113838 reveals.

Elliptical Curves

I recently read an interesting article in Quanta Magazine that involved elliptic curves. It's a fairly high level article but an excerpt read:

Their starting point was one of the central objects in number theory: elliptic curves. Just like circles and lines, elliptic curves are both numbers and shapes. They are pairs of numbers, \(x\) and \(y\), that serve as solutions to an algebraic equation like \(y^2 = x^3 − 2x\). The graph of those solutions creates a geometric shape that looks vaguely like a vertical line extruding a bubble.

This was followed by the diagram shown in Figure 1:

Figure 1

It turns out that these elliptic curves are very important in cryptography as this following YouTube video explained:

Many elliptic curves can be written as \(y^2=x^3+ax+b\) and all the curves shown in Figure 1 are of this type. What's of interest to me is that there are integer solutions to these sorts of equations, in other words there are points \( (x,y) \) such that \(x\) and \(y\) are both integers. These could be termed elliptic Diophantine equations.

Let's consider \(y^2=x^3-x+1\) as a particular example (the graph is shown in Figure 1, bottom left). When \(x=0\), \(y \pm 1\) but what about when \(y=0\)? Here we have \(x^3-x+1=0\) and there are three solutions, two complex and one real. What is the real solution? $${\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} - \frac{1}{2}\right)}^{\frac{1}{3}} + \frac{1}{3 \, {\left(\frac{1}{18} \, \sqrt{23} \sqrt{3} - \frac{1}{2}\right)}^{\frac{1}{3}}} \approx -1.3247$$So let's check what integral solutions there are between -1 and 100. Figure 2 shows the points that satisfy (permalink):

Figure 2

Extending the range to one million does not throw up any new points so these seem to be the only points that are integers. I have a book that deals with this very subject that is described as follows:

This book presents in a unified and concrete way the beautiful and deep mathematics - both theoretical and computational - on which the explicit solution of an elliptic Diophantine equation is based. It collects numerous results and methods that are scattered in the literature. Some results are hidden behind a number of routines in software packages, like Magma and Maple; professional mathematicians very often use these routines just as a black-box, having little idea about the mathematical treasure behind them. Almost 20 years have passed since the first publications on the explicit solution of elliptic Diophantine equations with the use of elliptic logarithms. The "art" of solving this type of equation has now reached its full maturity. The author is one of the main persons that contributed to the development of this art. The monograph presents a well-balanced combination of a variety of theoretical tools (from Diophantine geometry, algebraic number theory, theory of linear forms in logarithms of various forms - real/complex and p-adic elliptic - and classical complex analysis), clever computational methods and techniques (LLL algorithm and de Weger's reduction technique, AGM algorithm, Zagier's technique for computing elliptic integrals), ready-to-use computer packages. A result is the solution in practice of a large general class of Diophantine equations.

This is rather too detailed for me but the mention of Magma and Maple make me wonder what tools SageMath has to offer in terms of the solution of elliptic Diophantine equations. The book was published in August of 2013. As it turns out SageMath offers two commands. For the equation \(y^2=x^3+ax+b\), the commands are:

E=EllipticCurve([\(a,b\)])

E.integral_points()

For the case of \(y^2=x^3-x+1\), this produces the output (\(a\)=-1 and \(b\)=1):

[(-1 : 1 : 1), (0 : 1 : 1), (1 : 1 : 1), (3 : 5 : 1), (5 : 11 : 1), (56 : 419 : 1)]

The output is a little confusing but it would seem that the final 1 in each triplet signifies that the middle number can be positive or negative. It is thus equivalent to:

[(-1, ±1), ((0, ±1)), (1, ±1), (3, ±5), (5, ±11), (56, ±419)]

This is what is got earlier using my longer method. Elliptic curves is a big topic and I've only scratched the surface here. Figure 3 shows the points on the curve except for (56, ±419).

Figure 3: created using GeoGebra Classic

More on the Lambert W Function

I wrote about the Lambert W function in a post titled The Omega Constant and the Lambert W Function on June 24th 2020. Recently, I watched a blackpenredpen video that involved the use of the Lambert W function or the product log as it's sometimes called.

In the video, use was also made of Geogebra and WolframAlpha so this post repeats what is covered in the video and contains screenshots from both these resources. The video deals mainly with the solution of the equation: $$ \sqrt[3]{x}=\ln(x)$$Firstly, let's look at the graphs of \(y=\sqrt[3]{x}\) and \(y=\ln(x)\) using Geogebra. Figure 1 shows a screenshot.

Figure 1: generated using Geogebra

As can be seen in Figure 1, there are two solutions, \(x \approx 6.41\) and \(x \approx 93.35\). Now let's go about solving the equation:$$
\begin{align}
\sqrt[3]{x} &=\ln(x) \\
x^{1/3} &= \ln(x) \\
\ln(x).x^{-1/3} &=1 \\
-1/3. \ln(x).e^{-1/3. \ln(x)} &=-1/3 \\
W \big (-1/3 .\ln(x).e^{-1/3. \ln(x)} \big ) &=W \big (-1/3 \big ) \\
-1/3.\ln(x) &=W(-1/3)\\
x &= e^{-3.W_0(-1/3)} \text{ and } e^{-3.W_{-1}(-1/3) }\\
x & \approx 6.41 \text{ and } 93.35
\end{align}$$Figures 2 and 3 show how WolframAlpha will return the two approximations using the productlog function:

Figure 2

Figure 3

Figure 4 shows the commands needed in SageMathCell to produce these results:

Figure 4

UPDATE: I thought I'd add the following problems to this post rather than to create a new post. Here is the challenge: 

PROBLEM 1: Find the value of \(x\) for \(a^x=bx\) with \(a>1\) and \(b>1\). Test for \(2^x=8x\).

To solve this, let's take the log of both sides:$$
\begin{align}
\log(a^x) &=\log(bx)\\
x \log a &= \log(bx)\\
bx \log a &=b\log(bx)\\
e^{\log(bx)} \log a &=b\log(bx)\\
\frac{\log a}{b} &=\log(bx) \, e^{-log(bx)} \\
\frac{\log a}{b} &=- \log(bx) \, e^{-log(bx)} \\
W \big (\frac{\log a}{b} \big )&=W \big ( - \log(bx) \, e^{-log(bx)} \big )\\
W \big (\frac{\log a}{b} \big )&=-log(bx)\\
\log(bx) &=-W \big (-\frac{\log a}{b} \big )\\
bx&=e^{-W (-\frac{\log a}{b} ) }\\
x&=\frac{ e^{-W (-\frac{\log a}{b} )}}{b} \\
\end{align}$$When we substitute \(a=2\) and \(b=8\) we get:$$
x=\frac{ e^{-W (-\frac{\log 2}{8} )}}{8} \approx 0.1375$$Figure 5 taken from Geogebra confirms this result. \(f\) is \(y=2^x\), \(g\) is \(y=8x\) and A is given as (0,14, 1.1) by the program:

Figure 5

PROBLEM 2: Here is another equation that I came across on YouTube.$$x^2+\log(x)=0$$Here is the solution using the Lambert W function:$$ \begin{align}
x^2+\log(x) &=0\\
1+\frac{\log(x)}{x^2} &=0\\
\log(x) \, x^{-2} &=-1\\
-2 \, \log(x) \,x^{-2} &=2\\
\log(x^{-2}) \, e^{\log(x^{-2})} &=2\\
W(\log(x^{-2}) \, e^{\log(x^{-2})}) &=W(2)\\
\log(x^{-2}) &=W(2)\\
x^{-2} &=e^{W(2)}\\
x^2 &=e^{-W(2)}\\
x &=\sqrt{e^{-W(2)}}\\
x &\approx 0.6529
\end{align}$$Again, Geogebra confirms the result. See Figure 6.

Figure 6

THE ESUCARYS MAPPING

 I've written about the Collatz or \(3x+1\) mapping and similar mappings in earlier posts:

• The \(3x+1\) Problem on November 1st 2016
• The Collatz Conjecture Revisited on March 15th 2018
• The \(17x+1\) Map on March 18th 2018
• The PrimeLatz Conjecture on August 25th 2019
• Palindromic Cyclops Numbers on August 10th 2020

I wasn't aware that the Collatz conjecture is also referred to an the Syracuse problem.

The Syracuse problem, also known as the Collatz conjecture or the \(3n+1\) conjecture or Ulam conjecture, is a very simple problem of arithmetics that is still unsolved today. It can be stated as follows:

Syracuse problem: \(n \geq 1\) being an integer, repeat the following operations

• If the number is even then divide it by two
• If the number is odd then multiply it by 3 and add 1

Conjecture: This process always reaches the number 1

Today, in investigating the number properties of my diurnal age (26251), I discovered that it is a member of OEIS A129133:

A129133

Numbers whose trajectory under the Esucarys map ends at the fixed point 247.

The Esucarys sequence derives its name from a reversal of "Syracuse", with the generating rule being that for the Syracuse (\(3x+1\) or Collatz) sequence followed by a reversal. 247 is the only known fixed point of the Esucarys sequence. Very few numbers map to 247. The members of this sequence, up to 26251, are:

247, 1247, 1484, 2473, 4859, 5087, 5738, 7318, 7484, 9563, 9682, 9694, 9938, 11247, 12189, 12473, 14840, 14842, 15209, 15610, 16274, 16563, 16750, 16798, 17609, 19168, 20019, 21885, 24733, 26251

Here is a permalink to the SageMath algorithm to generate this sequence. As an example, in reaching 247, 26251 follows this trajectory:

26251, 45787, 263731, 491197, 2953741, 4221688, 4480112, 6500422, 1120523, 751633, 94522, 16274, 7318, 9563, 9682, 1484, 247

Here is a permalink to the SageMath algorithm that will generate this trajectory. Figure 1 shows a graph of this trajectory.

Figure 1

Primorial Number System

 I've written about the factorial number system in two previous posts:

• Factorial Number Base on March 31st 2018
• Factorial Number System on September 2nd 2020

It is a mixed radix number system and so is the primorial number system that uses the primorials (progressive products of primes):

• 2
• 2 x 3 = 6
• 2 x 3 x 5 = 30
• 2 x 3 x 5 x 7 = 210
• 2 x 3 x 5 x 7 x 11 = 2310
• 2 x 3 x 5 x 7 x 11 x 13 = 30030
• 2 x 3 x 5 x 7 x 11 x 13 x 17 = 510510
• 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 = 9699690 etc.

It's easy enough to set up an algorithm in SageMath that will convert decimal number to primorial digits. In decreasing order, the primorials below ten million are 9699690, 510510, 30030, 2310, 210, 30, 6 and 2. These numbers can serve as bases to represent any number up to 10,242,789 (which has representation as 111111111). Here is the algorithm (permalink) that will return the primorial base representation of any number up to 10,242,789. The example returns the representation for numbers from 2 to 50:

P=[9699690, 510510,30030,2310,210,30,6,2]

for number in [1..50]:

    original=number

    N=[]

    for p in P:

        N.append(number//p)

        number=number%p

    if is_odd(original):

        N.append(1)

    else:

        N.append(0)

    primorial=""

    for n in N:

        primorial+=str(n)

    print(original,"-->", int(primorial))

Primorial Formula

1 --> 1

2 --> 10

3 --> 11

4 --> 20

5 --> 21

6 --> 100

7 --> 101

8 --> 110

9 --> 111

10 --> 120

11 --> 121

12 --> 200

13 --> 201

14 --> 210

15 --> 211

16 --> 220

17 --> 221

18 --> 300

19 --> 301

20 --> 310

21 --> 311

22 --> 320

23 --> 321

24 --> 400

25 --> 401

26 --> 410

27 --> 411

28 --> 420

29 --> 421

30 --> 1000

31 --> 1001

32 --> 1010

33 --> 1011

34 --> 1020

35 --> 1021

36 --> 1100

37 --> 1101

38 --> 1110

39 --> 1111

40 --> 1120

41 --> 1121

42 --> 1200

43 --> 1201

44 --> 1210

45 --> 1211

46 --> 1220

47 --> 1221

48 --> 1300

49 --> 1301

50 --> 1310

Figure 1 shows a comparison of the factorial and primorial number systems:

Figure 1: source

The source for Figure 1 contains information on a wide range of unusual number systems which I may post about at some time in the future.

So what stimulated my interest in primorial number systems? Well, like most of my posts, it was prompted by my analysis of the number representing my diurnal age. Today I turned 26250 days old and this number has a striking factorisation:$$26250=7 \times 5^4 \times 3 \times  2$$The first entry for this number in the OEIS is A276086:

A276086

Prime product form of primorial base expansion of \(n\): digits in primorial base  representation of \(n\) become the exponents of successive prime factors whose product a(\(n\)) is.

It took me some time to understand what this meant. In the case of 26250, \(n\)=57 and its primorial base expansion is 1411. The resulting digits because the exponents of successive prime factors that multiply together to give 26250. In other words:$$7^1 \times 5^4 \times 3^1 \times 2^1 = 26250$$

Totient and Non-Totient Numbers

I've written about Euler's Totient Function in an eponymously titled post on March 12th 2019. Today however, my diurnal age number count of 26248 alerted me to the fact that this number was a member of OEIS A333020:

A333020

Starts of runs of 3 consecutive even numbers that are all totient numbers    (A002202).

This begged the question as to what a totient number was and as it turns out that:

A totient number is a value of Euler's totient function: that is, an \(m\) for which there is at least one \(n\) for which \( \phi(n) = m\). The valency or multiplicity of a totient number \(m\) is the number of solutions to this equation. A non-totient is a natural number which is not a totient number. Source.

Apart from 1, every totient number is even. This follows from the fact that every natural number is either prime or a product of primes and the totient of a prime number is one less than the number itself. For example, \( \phi(7)=6\) because 1, 2, 3, 4, 5 and 6 are coprime to it. All primes except 2 are odd and so the totient of all odd primes is even. Let's look at the totient numbers between 1 and 100:

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100 

There are 38 totient numbers between 1 and 100, thus 38%. Between 1 and 1000, there are 291 or about 29% and, between 1 and 10000, there are 2374 or about 24% and so. The percentage decreases as the range is extended. The Wikipedia article provides a formula for approximating this but I won't go into that here.

In my post from June of 2019, I looked at OEIS A001274:

A001274

Numbers \(k\) such that \( \phi(k) = \phi(k+1) \).

Such numbers are relatively infrequent as the following list shows:

1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545, 32864, 38804, 39524, 46215, 48704, 49215, 49335, 56864, 57584, 57645, 64004, 65535, 73124, 105524, 107864, 123824, 131144, 164175, 184635, ...

 Apparently, in 1999, the following was proved that:

for every integer \(k \geq 2 \) there is a totient number \(m\) of multiplicity \(k\): that is, for which the equation \( \phi(n) = m\) has exactly \(k\) solutions. However, no number \(m\) is known with multiplicity \(k = 1\). Source.

It's interesting to look at the distribution of these \(k\)s. For values of \(m\) up to one million, we find that \(m\)=241920 has a \(k\) value of 937. Figure 1 shows the distribution:

Figure 1: permalink

As can be seen, \(k\)=937 is quite an outlier. The next highest \(k\) value is 750. This means that up to the one million mark, there are no \(k\) values between 751 to 936 inclusive.

There are many sequences in the OEIS that relate to totient numbers. Here is one example:

A050495

Numbers that are the first term of at least one arithmetic progression with 4 or more terms all having the same value of Euler's totient function \( \phi(x) \).

The example is given of \( \phi(x) \)72 = \( \phi(x) \)(78) = \( \phi(x) \)(84) = \( \phi(x) \)(90) = 24, so 72 is a member of the sequence.

Figure 2 shows the totient numbers between 1 and 72, along with the numbers that produce these totient values:

Figure 2: source

Cunningham Numbers

I've come across Cunningham Chains before and written about them in several posts. However, I've not written about Cunningham Numbers before. These numbers always occur in pairs and the previous such pair was 25920 and 25922 that can be represented as \(161^2-1\) and \(161^2+1\) respectively. Today I turned 26243 days old and this is equal to \(162^2-1\) and the other member of the pair is 26245 equal to \(162^2+1\). So what defines such numbers. 

Here is a definition: Cunningham numbers are a simple type of binomial number, they are of the form$$b^n\pm1 \text{ where }b \text{ and } n \text{ are integers and }\\b \text{ is not a perfect power. They are denoted by }C^±(b,n)$$

Establishing whether or not a given Cunningham number is prime has been the main focus of research around this type of number. Two particularly famous families of Cunningham numbers in this respect are the Fermat numbers, which are those of the form \(C^+(2,2m) \), and the Mersenne numbers, which are of the form \( C^−(2,n) \).

Primes of the form \(C^±(b,n)\) are very rare. To quote from WolframAlphaMathWorld:

A necessary (but not sufficient) condition for \( C^+(2,n)=2^n+1\) to be prime is that \(n\) be of the form \(n=2^m\). Numbers of the form \(F_m=C^+(2,2^m)=2^{2^m}+1\) are called Fermat numbers, and the only known primes occur for:

• \(C^+(2,1)=3\)
• \(C^+(2,2)=5\) 
• \(C^+(2,4)=17\) 
• \(C^+(2,8)=257\)
• \(C^+(2,16)=65537\)

In other words for \(m=0, 1, 2, 3, 4 \). The only other primes \(C^+(b, n)\) for nontrivial \(b \leq 11\) and \(2 \leq n\leq 1000\) are:

• \(C^+(6,2)=37\) 
• \(C^+(6,4)=1297\) 
• \(C^+(10,2)=101\) 

\(C^+(2,n)=2^n+1\) is always divisible by 3 when \(n\) is odd. The Mersenne numbers \(M_n=C^-(2,n)=2^{n}-1\) are known to be prime only for 44 values, the first few of which are \(n=2, 3, 5, 7, 13, 17, 19, ... \) (OEIS A000043). Such numbers are known as Mersenne primes. There are no other primes \(C^-(b,n)\) for nontrivial \(b \leq 20\) and \(2\leq n\leq 1000\).

If primes are rare amongst the Cunningham numbers, then most are composite and thus factorable which leads us into the Cunningham Project:

The Cunningham project is a project, started in 1925, to factor numbers of the form \(b^n ± 1\) for \(b\) = 2, 3, 5, 6, 7, 10, 11, 12 and large \(n\). The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall. There are three printed versions of the table, the most recent published in 2002, as well as an online version.

Figure 1 shows the current limits of the exponents:

Figure 1

Two types of factors can be derived from a Cunningham number without having to use a factorisation algorithm: algebraic factors, which depend on the exponent, and Aurifeuillian factors, which depend on both the base and the exponent.

Perhaps, I'll explore the topic of factorisation of Cunningham numbers in more detail at a later date. For the moment, it can be noted that:

Once the algebraic and Aurifeuillian factors are removed, the other factors of \(b^n ± 1\) are always of the form \(2kn + 1\), since they are all factors of \(\displaystyle \Phi _{n}(b) \). 

When \(n\) is prime, both algebraic and Aurifeuillian factors are not possible, except the trivial factors \(b − 1\) for \(b^n − 1\) and \(b + 1\) for \(b^n + 1\).

In general, all factors of $$ \frac{b^n − 1}{b − 1}$$ are of the form \(2kn + 1\), where \(b ≥ 2\) and \(n\) is prime, except when \(n\) divides \(b − 1\), in which case $$ \frac{b^n − 1}{b − 1}$$ is divisible by \(n\) itself.

Of course, for the pairs of Cunningham numbers mentioned earlier ((25920, 25922) and (26243, 26245)), the value of \(n\) is 2 and hence prime. This means that there are no algebraic or Aurifeuillian factors, only the trivial factors and factors to the form \(4k+1\). The factorisations are:

• \(25920 =161^2-1=160 \times 162=2^6 \times 3^4 \times 5\) 
• \(25922 =161^2+1=2 \times 13 \times 997\) 
• \(26243 = 162^2-1=161 \times 163=7 \times 23 \times 163 \)
• \(26245 = 162^2+1=5 \times 29 \times 181\)

Hamiltonian Paths and Knight's Tours

I encountered Hamiltonian paths before but never in the context of my daily number count. The reason is clear when we look at Figure 1 showing the initial members of OEIS A003216:

A003216

Number of Hamiltonian graphs with \(n\) nodes.

Figure 1: source

Looking at Figure 1, it can be seen that \(n\)=8 yields a value of 6196 but \(n\)=9 yields a value of 177083. This is a massive jump that completely misses the numbers that I am traversing as I track my diurnal age. Currently I am 26241 days old and one of the properties of this number is that it is a member of OEIS A283420 where \(n\)=9:

A283420

Number of simple (not necessarily connected) untraceable graphs on \(n\) nodes.

Even in the A283420 sequence the numbers get large very quickly. Here are the values from \(n\)=1 to 11: 0, 1, 2, 6, 16, 65, 310, 2316, 26241, 522596, 18766354. My current diurnal age just happened to be a member of this sequence and this is what led me to reacquaint myself with Hamiltonian graphs. Figure 2 shows all the possible non-Hamiltonian graphs for the case of \(n\)=5:

Figure 2: source

Looking at Figure 2, the distinction between graphs that are connected and those that are disconnected is apparent. But what about the terms simple and untraceable? At this point, it's a good idea to define separately what is meant by a simple graph and traceable graph (which will then explain an untraceable graph).

To quote from WolframMath World:

A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges. A simple graph may be either connected or disconnected. Figure 3 shows the differences between a simple graph and a nonsimple one:

Figure 3: source

A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. The numbers of traceable graphs on \(n\)=1, 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph \(K_1\) is conventionally considered traceable. The first few are illustrated in Figure 4, with a Hamiltonian path indicated in orange for each. Source.

Figure 4: source

Comparing Figures 2 and 4, it can be seen what it is that defines a Hamiltonian path and a Hamiltonian cycle:

A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a traceable graph ... A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Source.

Figure 5 shows a Hamiltonian cycle for the dodecahedron. 

Figure 5: source

A knight's tour can be viewed as either a Hamiltonian cycle or path when each square is regarded as a vertex:

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open. The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time. Source.

Figure 6 shows an open knight's tour that is a Hamiltonian path but not a cycle:

Figure 6: source

It has been shown that closed knight's tours are possible on any \(m\) x \(n\) board with \(m\) ≤ \(n\) unless one or more of these three conditions are met:

• \(m\) and \(n\) are both odd
• \(m\) = 1, 2, or 4
• \(m\) = 3 and \(n\) = 4, 6, or 8

On an 8 × 8 board, there are exactly 26,534,728,821,064 directed closed tours (i.e. two tours along the same path that travel in opposite directions are counted separately, as are rotations and reflections). The number of undirected closed tours is half this number, since every tour can be traced in reverse. Source. 

Finally let's not fail to mention the great mathematician, Sir William Rowan Hamilton, after whom the Hamiltonian paths and cycles were named. Figure 7 shows a photograph of him.

Figure 7: Hamilton (1805-1865)

For a brief account of his life, follow this link.