Problems & Puzzles: Puzzles

Puzzle 1001. Anti-divisors of prime numbers   As far as I know the concept of "anti-divisor" was created and studied by Jon Perry around 2001.   Let's start by the anti-divisor's definition. From the sequence A066272: Definition: If an odd number i in the range 1 < i <= n divides N where N is any one of 2n-1, 2n or 2n+1 then d = N/i is called an anti-divisor of n. The numbers 1 and 2 have no anti-divisors. Equivalently, an anti-divisor of n is a number d in the range [2,n-1] which does not divide n and is either a (necessarily odd) divisor of 2n-1 or 2n+1, or a (necessarily even) divisor of 2n. Thus an anti-divisor of n is an integer d in [2,n-1] such that n == (d-1)/2, d/2, or (d+1)/2 (mod d), the class of d being -1, 0, or 1, respectively. k is an anti-divisor of n if and only if 1 < k < n and | (n mod k) - k/2 | < 1. If you need them, Jon Perry wrote two web pages explaining and developing other issues in detail about the anti-divisors. See here a & b.   Here are the anti-divisors for all the numbers from 1 to 100   n Anti-divisors 1 none 2 none 3 2 4 3 5 2.3 6 4 7 2.3.5 8 3.5 9 2.6 10 3.4.7 11 2.3.7 12 5.8 13 2.3.5.9 14 3.4.9 15 2.6.10 16 3.11 17 2.3.5.7.11 18 4.5.7.12 19 2.3.13 20 3.8.13 21 2.6.14 22 3.4.5.9.15 23 2.3.5.9.15 24 7.16 25 2.3.7.10.17 26 3.4.17 27 2.5.6.11.18 28 3.5.8.11.19 29 2.3.19 30 4.12.20 31 2.3.7.9.21 32 3.5.7.9.13.21 33 2.5.6.13.22 34 3.4.23 35 2.3.10.14.23 36 8.24 37 2.3.5.15.25 38 3.4.5.7.11.15.25 39 2.6.7.11.26 40 3.9.16.27 41 2.3.9.27 42 4.5.12.17.28 43 2.3.5.17.29 44 3.8.29 45 2.6.7.10.13.18.30 46 3.4.7.13.31 47 2.3.5.19.31 48 5.19.32 49 2.3.9.11.14.33 50 3.4.9.11.20.33 51 2.6.34 52 3.5.7.8.15.21.35 53 2.3.5.7.15.21.35 54 4.12.36 55 2.3.10.22.37 56 3.16.37 57 2.5.6.23.38 58 3.4.5.9.13.23.39 59 2.3.7.9.13.17.39 60 7.8.11.17.24.40 61 2.3.11.41 62 3.4.5.25.41 63 2.5.6.14.18.25.42 64 3.43 65 2.3.10.26.43 66 4.7.12.19.44 67 2.3.5.7.9.15.19.27.45 68 3.5.8.9.15.27.45 69 2.6.46 70 3.4.20.28.47 71 2.3.11.13.47 72 5.11.13.16.29.48 73 2.3.5.7.21.29.49 74 3.4.7.21.49 75 2.6.10.30.50 76 3.8.9.17.51 77 2.3.5.9.14.17.22.31.51 78 4.5.12.31.52 79 2.3.53 80 3.7.23.32.53 81 2.6.7.18.23.54 82 3.4.5.11.15.33.55 83 2.3.5.11.15.33.55 84 8.13.24.56 85 2.3.9.10.13.19.34.57 86 3.4.9.19.57 87 2.5.6.7.25.35.58 88 3.5.7.16.25.35.59 89 2.3.59 90 4.12.20.36.60 91 2.3.14.26.61 92 3.5.8.37.61 93 2.5.6.11.17.37.62 94 3.4.7.9.11.17.21.27.63 95 2.3.7.9.10.21.27.38.63 96 64 97 2.3.5.13.15.39.65 98 3.4.5.13.15.28.39.65 99 2.6.18.22.66 100 3.8.40.67   Now we will turn to our puzzle for this week.   Paolo Lava wrote on May 3: Take the sum of anti-divisors of a prime P, SAD(P): if it is a prime repeat the process. I have found primes that produce only one prime through this process. The first ones are 3, 13, 113, 761, 1201, 1741, 1861, 2113, 9661, 9941, 12641, 13613, 15313, 21841, 23981, 30013, 34061, 47741, 49613, … E.g. Anti-divisors of 13 are 2, 3, 5, 9 and their sum is 19 that is prime. But anti-divisors of 19 are 2, 3, 13 and their sum is 18 that is not prime. Anti-divisors of 1861 are 2, 3, 17, 51, 61, 73, 219, 1241 and their sum is 1667 that is prime. But anti-divisors of 1667 are 2, 3, 5, 11, 23, 29, 33, 101, 115, 145, 303, 667, 1111 and their sum is 2548 that is not prime. BTW, the primes 5 and 41 are special in the sense that these are the only two already known primes that its respectively sum is equal to the given prime: SDA(5)=2+3=5; SAD(41)=2+3+9+27=41 BTW, Paolo computed SAD(P)=Q, P&Q primes until P=99616613.. Here is his file. Q1. Are there primes that produce two or more primes in sequence by the sum of their anti-divisors, other than 5 & 41? After I received the puzzle proposal from Paolo, I started my own computations for SAD(P)=Q, P&Q primes. Here is my file for 99,999,999<P<999,999,999, and also five more questions: Q2. Are there other primes as 5 & 41?. See first A073930. Q3. Can you explain why all the primes P>5 such that SAD(P)=Q,  {P, Q}=prime, are such that P@10={1 or 3} My largest quotient Q/P is this one: P=352849613, Q=989182003, Q/P=2.80340963. Q4. Send a larger one quotient Q/P. Jon Perry observes that: "The pattern of anti-divisors is as random and incomprehensible as that with prime numbers...[more over] every number has a unique set of anti-divisors." Let's take for granted that anti-divisors resemble prime integers, as Perry notes, in whole aspects not only in the two mentioned issues above. As perhaps you already know, there are a minimal set S of exactly 26 prime numbers with the following interesting property: "Any prime or is already a member of S or it can be transformed to at least one of these 26 primes in S, by the simple and only procedure of eliminating one or several digits". S = {2,3,5,7,11,19,41,61,89,409,449,499,881,991,6469,6949, 9001,9049, 9649,9949,60649,666649,946669,60000049, 66000049,66600049} This was proved by Jeffrey Shallit in 1999. See his proof here. See also A071062 and see my Puzzle 178. Q5. Can you find the corresponding minimal set S of anti-divisors for all the anti-divisors? Jon Perry also noted that "integers with only one anti-divisor are rare, and include 3,4,6,96 and 393216". See A066466.   Q6. Can you find the sixth term to A066466?

---

Over the week 16-22, May 2020, contributions came from Emmanuel Vantieghem, Jan van Delden and Oscar Volpatti

 

***

Emmanuel wrote:

Q1.
I extended Paolo's list up to  2*10^14 (explanation of how I could go so far comes a bit later).
This allowed me to say that besides 5 and 41 there is no prime  p  below  2*10^14  such that  SAD(p)  and  SAD(SAD(p))  are both prime.
This answers Q2 at the same time.

Q3.
Let  p  be an odd prime.  From the definition of anti-divisor we can deduce :
   SAD(p) = Sigma(2p-1) + Sigma(2p+1) - 4p,
where Sigma(m) is the sum of the divisors of  m.
When  SAD(p) is odd, then one and only one of the two numbers Sigma(2p-1) or Sigma(2p+1) is odd.
But, the sum of the divisors of an odd number is odd if and only if that number is a perfect square.
Thus, for  SAD(p)  to be ODD, either  2p-1  or  2p+1  must be a perfect square !
Clearly, 2p+1 cannot be a square (its is == 3 mod 4).  Thus, 2p-1  is a perfect square.
Now, when 2p-1  is a perfect square, it must be congruent to 1, 5 or 9 mod 10.
But then, 2p must be congruent to  2, 6 or 10 mod 10.
The first two congruences lead to  p == 1 or 3 mod 5.  But since p is odd, we then have p = 1 or 3 mod 10.
The last congruence only holds when  p = 5.
This explains why the end digit of  p  is always 1 or 3  when SAD(p) is prime..

Q4.
The preceding consideration allowed me to extend Paolo's list to 2*10^14 in a reasonable time.
When p is in that list, the maximum for  q/p  is  3.5153  and is reached when p = 64938795534113, q = 228279530695669.

What is the maximum ever possible value for Q/P in Q4?? [CR]
 

My answer : 

I have no idea.

But, if there is a bound   B  on the value of  Sigma(m) / m, then there is also a bound on  Q/P  (which will be about  7B - 6). But I do not know of any bound for  Sigma(m) / m.

...

The bound "7B - 6" in my last mail should be  "6B - 6".

Of course now I owe you a complete derivation.  Here it comes :

 

Let  m = u 2^k  with  u  odd.  Then we have (I abbreviate  "Sigma"  by  "S") :

SAD(m) = S(2m-1)+S(2m+1)+S(u)2^(k+1) - 6m - 2

(you can get numerical evidence of this if needed). 

Thus, if  S(x) < Bx  for all x (using the fact that S(u)2^(k+1) = S(u)(S(2^k)+1) = S(m)+S(u) <= 2S(m) ) :

SAD(m) < B(2m-1)+B(2m+1)+2Bm - 6m = (6B - 6)m.
 

Thus, SAD(m)/m < 6B - 6.

Q5.
It is easy to show that every number  k  is anti-divisor of some  n :
     * if  k  is odd, we can take  n  to be   (3k + 1)/2
     * if  k  is even we can take  n  to be  3k/2
Thus, the set of all anti-divisors is the set of all natural numbers greater than 2.  So, no such  S  exist.
     
Q6.
In  A066466  it is explained that the number of anti-divisors of  n (> 4) equals 1  iff  n  is of the form  3*2^k  with  k  such that 3*2^(k+1) -1  and  3*2^(k+1) + 1 are both primes.
It is known from the comment line in  A066466  that there are no other such  k  up to  5000000. Therefore the next element of  A066466 (if it exists) is greater than  3*2^5000000 which is about 10^1505150.
For me impossible to find in a reasonable time ....

***

Jan wrote:

Q2

 

These primes p are such that 2p-1=3^k for some k and 2p+1 prime. It is not hard to show that given these conditions, that k=2, k=4 are the only values that solve SAD(p)=p. But this doesn't answer the question in full.

 

Q3

 

For an odd prime number p we have that 2p only has p as on odd divisor, thereby contributing the only antidivisor 2. In order to have an odd sum of antidivisors, SAD(p), we need an odd number of odd divisors of 2p-1 and 2p+1, smaller than p. That means that either 2p-1 or 2p+1 must have an odd number of (odd) divisors.

 

Every number n can be written as product of its prime factors q[i] by the product(q[i]^m[i],i=1..k), where m[i] is the multiplicity. The number of divisors is now equal to the product((m[i]+1),i=1..k). These divisors include 1 and the number n itself. We need to subtract these in order to find divisors d for which 1<d<n. This does not affect the parity. We thus find that n has an odd number of divisors if and only if the multiplicity m[i] of every prime factor q[i] is even. In other words: we need n to be a square.

 

The number 2p+1 can never be a square. This is certainly true if p=2. Suppose we write 2p+1=x^2 with p odd and larger than 2. We must have that x is odd and larger than 2 and 2p=(x-1)(x+1). But 2 is a divisor of both x-1 and x+1, which would make p even. Contradiction.

 

The number 2p-1=x^2 can only be a square if x=1,3,5 mod 10. This is a simple check. The only prime that is congruent to 5 mod 10 equals 5 itself.

 

We thus seek primes p for which 2p-1 is a square, which I didn't realise when I wrote my first routine. It could have saved me quite some primality tests, if I figured this one out earlier.

 

Q4

 

I found p=97194200513,q=301825618639 with quotient 3.1053871223. I searched until 417*2^28 about 1*10^11.

 

In order to find a large quotient we need highly composite numbers 2p-1 or 2p+1. Finding two is probably too much to ask for, my money is on 2p-1 (since it needs to be a square, it already has 'extra' factors). In this case we have 2p-1=3^2*5^2*7^2*13^2*17^2*19^2. This factorisation alone is already responsible for a factor  3.058875494. Unfortunately 2p+1=43*4520660489, so it's contribution is much smaller (approximately 2/43).

 

The ratio defined by I(n)=sigma(n)/n, i.e. the sum of the divisors of n divided by n, is called the abundancy index. It can  grow without bounds, we have I(k*n)>I(n) if k>1 (Richard Laatsch, 1986).

 

The smallest odd number that has I(n)>3 equals 1018976683725, but is not a square.

 

We are interested in J(p)=(sigma(2p-1)-2p)/p=sigma(2p-1)/(2p-1)*(2p-1)/p-2, which is slightly less than 2(I(2p-1)-1).

 

Constructing highly composite squares x^2 and checking whether p=(x^2+1)/2 is prime and finally if SAD(p) is prime could be a plan of attack of finding large values for q/p.

Furthermore we already know the contribution of 2p and 2p-1 to SAD(p). Only the prime factors of 2p+1=x^2+2 are necessary to compute q. These factors are probably not 'evenly' distributed, we could use this to choose a factorisation technique.

 

Given the prime factors in 3..37 and limiting the multiplicity to 6, I could find:

 

x^2=3^6*5^4*7^6*11^6*13^6*17^4*19^2*23^2*29^2*31^4*37^2, p=(x^2+1)/2, SAD(p)/p=4.7810759740

Here 2p+1=x^2+2=59*67*29010361*116927415499*579722947214248943946481

 

Belonging to:

 

p=3886751667861900743541032780064866451044590313

q=18582855015292209133489736872519112113017021403

 

Larger values of SAD(p)/p can be obtained similarly. Just choose more prime factors and/or increase the maximum value for the multiplicity.
A word of warning though: If you choose k prime factors out of n, and each multiplicity out of a set m is used the number of options to test equals Binom(n,k)*m^k.

 

...

 

A small addendum with regard to Q4.

 

sigma(2p-1) equals (2p-1) prod((q[i]-1/q[i]^m[i])/(q[i]-1), if the q[i],m[i] increase, the term 1/q[i]^m[i] can be neglected and we arrive at:

 

J(p)=(sigma(2p-1)-2p)/p is approximately 2( prod(q[i]/(q[i]-1)-1)

 

This is independent of the m[i], but the approximation is better for larger m[i]. Small primes q[i] have a large impact on J(p).

A small test reveals that if we study a list of consecutive primes starting at 3 and ending at some prime q[n], we need:

 

The primes 3..5 for ratio 1.
The primes 3..7 for ratio 2.
The primes 3..13 for ratio 3.

The primes 3..23 for ratio 4.
The primes 3..43 for ratio 5.
The primes 3..79 for ratio 6.

 

One may roughly estimate the size of ln(prod(q[i]/(q[i]-1))=-sum(ln(1-1/q[i])) by sum(1/q[i]) (*), use that q[i] is approximately i*ln(i) and arrive at:

 

J(p) is approximately equal to 2*ln(n), where n is the index of the largest prime q[n] used.

 

For those of you who checked this, my initial approximation would have been 2(ln(n)-1), but I discarded a ‘few’ terms in (*).
In order to arrive at a ratio equal to r, based on the divisors of 2p-1 and on this rough estimate would entail using consecutive prime factors from 3 until

 

(r/2) exp (r/2)

 

A lot of ifs and buts, but it gives some perspective on the number of computations involved.

***

Oscar wrote:

Q3
Let P = 2*X+1 be an odd prime greater than 3; its anti-divisors are:
the even prime number 2; 
the odd divisors of N1 = 4*X+1 = 2*P-1, excluding 1 and N1 itself;
the odd divisors of N3 = 4*X+3 = 2*P+1, excluding 1 and N3 itself.
As the prime number 3 doesn't divide P, it divides either N1 or N3, so the sum Q = SAD(P) is at least 5;
if Q is prime, it must be an odd prime.
As the divisors of N3 come in pairs  (d, N3/d), their contribution to SAD(P) is even.
The same holds for the divisors of N1, so that SAD(P) is even too, unless we have an odd perfect square N1 = M^2.

Now, consider the odd residue classes M mod 10.

M % 10 = 1 or 9:
N1 % 20 = 1   and   P % 10 = 1;

M % 10 = 3 or 7:
N1 % 20 = 9   and   P % 10 = 5;

M % 10 = 5:
N1 % 20 = 5   and   P % 10 = 3.

The only prime ending in 5 is 5 itself; any other prime P must end in 1 or in 3.

Q4
We can ensure that N1 has many divisors by forcing M to have many small prime factors.

M = 3 * 5 * 7 * 11 * 13 * 47;
P = 249009773513;
Q = 764358966037;
R = 3.069594238...

M = 3^2 * 5 * 7 * 11^2 * 13 * 23;
P = 64938795534113;
Q = 228279530695669;
R = 3.515302814...

Q5
Every integer d>1 is an anti-divisor. Consider the list of the first 10 anti-divisors:
S = {2,3,4,5,6,7,8,9,10,11}
Its elements can't be reduced to shorter numbers, as 0 and 1 are not anti-divisors.
For every integer d>11:
if d contains a digit in the range 2-9, keep that digit;
otherwise, the first two digits of d must be 10 or 11, and we can keep them.

Q6
Next element must be a number of the form n = 3*2^(k-1), where both (3*2^k)-1 and (3*2^k)+1 are primes.
All exponents up to about 15000000 have been tested, no twin primes have been found so far. 

***