Thursday 20 December 2018

A Prime to Remember

Primes come and go but lately, as I keep a daily track of the number of my diurnal days, there has been more than usual. To illustrate, days 25447, 25453, 25457, 25463, 25469, and 25471 are all primes in a 6-4-6-6-2 pattern. After 25471 there will quite a drought because the next prime is 25523, a gap of 32.

Today I'm 25463 days old and I can't let it pass without recording some of its more interesting properties. One of these is that it is a member of OEIS A165572: the greater prime factor of successively better Golden Semiprimes. These semiprimes p*q, starting from 6=2*3, have the property that each successive value of q/p gives a better approximation of the Golden Ratio than the previous term where the $$ \text{Golden Ratio } \phi=\frac{1+\sqrt(5)}{2} \approx \, 1.61803398874989$$Here are the initial members of this sequence: 3, 5, 11, 31, 37, 47, 157, 571, 911, 1021, 1487, 2351, 3571, 24709, 25463. The corresponding semiprimes form OEIS A165570 and consist of 6, 15, 77, 589, 851, 1363, 15229, 201563, 512893, 644251, 1366553, 3416003, 7881197, 377331139, 400711231, 2963563859, 4035221017.

Here are the progressively better approximations as the larger factor of the semiprime is divided by the smaller:

3/2         1.50000000000000
        5/3         1.66666666666667
        11/7         1.57142857142857
    31/19         1.63157894736842
      37/23         1.60869565217391
     47/29         1.62068965517241
157/97         1.61855670103093
  571/353         1.61756373937677
    911/563         1.61811722912966
1021/631         1.61806656101426
1487/919         1.61806311207835
 2351/1453         1.61803165863730
  3571/2207         1.61803352967830
 24709/15271         1.61803418243730
25463/15737         1.61803393276991

Another property of 25463, albeit a base dependent one, is its membership in OEIS A156119: primes formed by rearranging five consecutive decimal digits (avoiding leading 0). No primes can be formed from {1,2,3,4,5} or {4,5,6,7,8} since they are divisible by three. Sequence is finite, ending with a(52)=96857. Initial members of sequence are: 10243, 12043, 20143, 20341, 20431, 23041, 24103, 25463.

Yet another property, again base dependent, is its membership of OEIS A124629: primes p such that their cubes are pandigital, meaning all digits from 0 to 9 must appear at least once; here 25463^3=16509301927847. The initial members of this sequence are: 5437, 6221, 7219, 8443, 10903, 11353, 15937, 17123, 18229, 19429, 20353, 20903, 20929, 21803, 21841, 21961, 22123, 22283, 22993, 23053, 23369, 23663, 24733, 25183, 25219, 25463.

Not base dependent is the property that 25463 shares as a member of OEIS A226154: smallest of four consecutive primes whose sum is a triangular number. Triangular numbers are of the form:$$ \binom{n}{2}= \frac{n \, (n-1)}{2}$$The initial members of this sequence are: 5, 23, 191, 389, 449, 2593, 3011, 5167, 5639, 5851, 8669, 18839, 25463. Here the four primes add to 101926 = 25463+25469+25471+25523 and this sum is a triangular number because: $$101926 = \binom{452}{2}=\frac{452 \times 451}{2}$$ 

Finally and again base independently, 25463 is a member of OEIS A022121: Fibonacci sequence beginning 3, 8. The initial members of this sequence are: 3, 8, 11, 19, 30, 49, 79, 128, 207, 335, 542, 877, 1419, 2296, 3715, 6011, 9726, 15737, 25463.

Random Walks

Let's consider the following situation. We start at the origin (0,0) and want to get to the point (4,4). However, we can only move one step at a time, either horizontally or vertically. We are constrained to move within the grid of points shown. Given this constraint, horizontal movement can be to the left or right and vertical movement can be up or down. However, we have no control over this step by step movement. It is completely random. On average, how many steps should be required to reach our destination?

FIGURE 1

I set up a program in SageMathCell to simulate this random walk over 1,000 trials. The result returned a median walk of 60 steps. What happens as the grid grows larger? I was interested in looking at the relationship between the size of the grid and the average number of steps required to reach the goal. Here are the results for grids with of size 1 to 21 and a graphical representation in FIGURE 2:

1234567891011
2143460108156224289388534587


12131415161718192021
76288411041270142016571785211424422693


FIGURE 2

Not surprisingly the graph seems to be that of a parabola and my best fit formula, based on the above data, gives its equation as \(y=5.2 \, x^2\). 

This type of walk can be extended to 3 dimensions so that from (0, 0, 0) we need to get to (2, 2, 2) for example:

FIGURE 3

Running a thousand trials again on SageMathCell again, we get a median of 40 steps with a minimum of 6 (the least possible) and a maximum of 344. What's surprising is the vastly different lengths of these random walks. For example, with a cube of side 10, a median of 3075 steps is returned from the thousand trials but the maximum is 46826 and the minimum is 114. Here are the results (the simulation was too slow for sides greater than 10):

12345678910
7401172544737931129178623903075

FIGURE 4

Although it looks parabolic, it's probably cubic and, if this is the case, then an equation of \(y=0.27 \, x^3 \) seems the best fit. In any case, this post is not meant to be definitive. It's just meant to clarify my thinking. I'll need to pursue this further and improve on the accuracy of these possible equations.

Saturday 15 December 2018

Primitive Abundant Numbers

Preliminary note: I've written about odd primitive abundant numbers in an earlier, eponymous post from May 21st 2017, so some content from that post is repeated here but there is new content as well. Here is the link.

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

The sum of the proper divisors of an abundant number is greater than the number itself. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. So what is a primitive abundant number?

To quote from Numbers Aplenty:
An abundant number is called primitive if none of its proper divisors is abundant. 
There are infinitely many such numbers, both even and odd. However Dickson proved that there are only a finite number of odd primitive abundant numbers with a given number of distinct prime factors. 
For example, there are only 8 odd primitive abundant numbers with 3 distinct prime factors, namely, 945, 1575, 2205, 7425, 78975, 131625, 342225, and 570375. 
The first primitive abundant numbers are 12, 18, 20, 30, 42, 56, 66, 70, 78, 88, 102, 104, 114, 138, 174, 186, 196 more terms. 
A second definition of primitive numbers excludes also those that have perfect proper divisors, like all multiples of 6. The first such numbers are 20, 70, 88, 104, 272, 304, 368, 464, 550, 572, 650, 748, 836, 945, 1184, 1312, 1376, 1430, 1504, 1575, 1696, 1870, 1888, 1952, 2002.
Here are some properties of primitive abundant numbers taken from Wikipedia:
Every multiple of a primitive abundant number is an abundant number. 
Every abundant number is a multiple of a primitive abundant number or a multiple of a perfect number. 
Every primitive abundant number is either a primitive semiperfect (also called primitive pseudoperfect) number or a weird number. 
There are an infinite number of primitive abundant numbers. 
The number of primitive abundant numbers less than or equal to \(n\) is \( o \left( \frac{n}{\log^2(n)} \right)\ \). 

A semiperfect or pseudoperfect number is a natural number that is equal to the sum of all or some of its proper divisors. A primitive semiperfect number (also called a primitive pseudoperfect number, irreducible semiperfect number or irreducible pseudoperfect number) is a semiperfect number that has no semiperfect proper divisor. The first few primitive semiperfect numbers are 6, 20, 28, 88, 104, 272, 304, 350, ... There are infinitely many odd primitive semiperfect numbers, the smallest being 945.

A weird number is a natural number that is abundant but not semiperfect or pseudoperfect. In other words, the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of those divisors sums to the number itself. The first few weird numbers are 70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792, 10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, 13790, 13930, 14770, ...

See my blog post titled Zumkellar, Half-Zumkellar, and Pseudoperfect Numbers and Odd Primitive Abundant Numbers.

Tuesday 4 December 2018

Admirable Numbers and Compatible Numbers

Yesterday I turned 25446 days and this number was identified by Numbers Aplenty as an admirable number, defined as a number \(n\) for which there exists a divisor \(d\) of \(n\) such that \(2n = \sigma(n)-2d\). In other words, \(n\) is equal to the sum of its proper divisors, where one of them has a minus sign.

For 25446, the divisors are: 1, 2, 3, 6, 4241, 8482, 12723, 25446 and the sum of these divisors is 50904. However, 50904 - 2 x 6 = 50892 = 2 x 25446 and here the divisor 6 has been assigned the minus sign. The modified divisors (1, 2, 3, -6, 4241, 8482, 12723) now add to 25446. The previously mentioned website goes on to say that:
Clearly, admirable numbers are a subset of abundant numbers and they are infinite because, for example, all the numbers 6\(p\), with \(p\)>3 prime, are admirable. The largest number that cannot be written as a sum of admirable numbers is 1003. Pairs of consecutive admirable numbers are rarer than pairs of consecutive abundant numbers. Up to \(10^{12}\), there are only two such pairs, namely 29691198404, 29691198405 and 478012798575, 478012798576.
On the other hand, pairs of admirable numbers that differ by two are more common but still sparse. There are 72 such pairs up to 27000.
 

The smallest 3 x 3 magic square made up of admirable numbers is shown in Figure 1.

Figure 1: smallest possible magic square
made from admirable numbers

OEIS A111592 lists the initial admirable numbers:
12, 20, 24, 30, 40, 42, 54, 56, 66, 70, 78, 84, 88, 102, 104, 114, 120, 138, 140, 174, 186, 222, 224, 234, 246, 258, 270, 282, 308, 318, 354, 364, 366, 368, 402, 426, 438, 464, 474, 476, 498, 532, 534, 582, 606, 618, 642, 644, 650, 654, 672, 678, 762, 786, 812, ...
These numbers are related to Zumkellar, Half-Zumkellar and pseudoperfect numbers in that they all involve the divisors of the number. See my blog post on these sorts of numbers.

In the OEIS comments, we read that "the concept of admirable numbers was developed by educator Jerome Michael Sachs (1914-2012) for a television in-service training course in mathematics for elementary school teachers." Here is the link to the article that he wrote in The Arithmetic Teacher, Vol. 7, No. 6 (1960), pp. 293-295. However, in that article he allows more than one of the divisors of a number to be negative. For example, he writes 24 as being equal to the following algebraic sum of its divisors: 4+6+8+12-1-2-3. However, this is the same as 1+2+3+4+8+12-6 so it's not clear whether a sum involving multiple negative divisors is always equivalent to another sum involving a single negative divisor.

Sachs also introduces the notion of a compatible number pair as an extension or relaxation of the concept of an amicable number pair. For example, 220 and 284 are an amicable pair because the proper divisors of each add to the other number. The proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 and these add to 284. The proper divisors of 284 are 1, 2, 4, 71 and 142 and these add to 220. In such cases, the smaller number is abundant and the larger number deficient.

Sach's proposal for a compatible number pair is two numbers such that the algebraic sums of their divisors each leads to the other number. For example:
  • 30 has divisors of 1, 2, 3, 5, 6, 10, 15
  • 40 has divisors of 1, 2, 4, 5, 8, 10 and 20
  • 40 = 2 + 3 + 5 + 6 + 10 + 15 - 1
  • 30 = 1 + 2 + 4 + 5 + 8 + 20 - 10
So he defines 30 and 40 as compatible numbers.

The smaller members of such pairs are listed in OEIS A109797 while the larger members are listed in OEIS A109798.

Here is the SageMath code to generate the admirable numbers between 25000 and 26000