Problems & Puzzles: Puzzles

Puzzle 360. Complementary divisors to make a prime Parviz Afereidoon sent the following puzzle: Find numbers N such that for each and all divisor d of N, |d+d'| and |d-d'| are no-composite numbers (1 or prime), where d'= N/d. Parviz has found the following first five N values satisfying the above condition: 2, 6, 30, 42 & 462. He also observes that: a) for N>3, N must be of the form 6k. b) all computed solutions are the product of two consecutive numbers Questions: 1. Find the next N value in this sequence. 2. Explain the properties a) & b), if they are necessary characteristics.

---

Contribution came from Farideh Firoozbakht.

***

Farideh wrote:

We can easily prove that all terms of the sequence are square free

Answer to Q1: I guess that the sequence is finite and 462 is the largest term.

 

Answer to Q2:  If n > 4 and n is a term of the sequence then n/1-1 & n/1+1 are primes so  n must be even and if 3 doesn't divide n then 3 divides at least one of the  two primes n-1 or n+1 so 3=n-1 or 3=n+1 which is a contradiction, because  n>4. Hence 6 divides n.
 

In fact by similar reasons, we can prove that,  " If n is a term of the sequence greater than 462, then 2*3*7*11 divides n."

 

Also there is no any reason that if n is a term of the sequence which is greater than 462 then n is product of two consecutive numbers.

 

1. All terms are square free. 

 

Proof: If for a prime p, n=k*p^2 and d = p then d' = k*p  so both numbers

d' + d = p(k+1) & d' - d =p(k-1) are composite, hence n can't be in the sequence.

 

2. If n>462 and n is a term of the sequence then 2*3*7*11=462 divides n.

 

Proof: We know n = 6*m so m > 462/6 = 77 according to the definition since

n = 1*6m = 2*3m = 3*2 m = 6*m, all the eight numbers  6m - 1, 6m + 1, 3m - 2,

3m + 2, 2m - 3, 2m + 3, m - 6, m + 6  are prime and all of them are greater than 7.

 

7 doesn't divide m - 6  so m isn't of the form 7t - 1.

7 doesn't divide m + 6  so m isn't of the form 7t + 1.

7 doesn't divide 2m - 3  so m isn't of the form 7t - 2.

7 doesn't divide 2m + 3 so m isn't of the form 7t + 2.

7 doesn't divide 3m + 2  so m isn't of the form 7t - 3.

7 doesn't divide 3m - 2  so m isn't of the form 7t + 3.

 

So m is of the form 7t hence n = 2*3*7*t and t>462/42=11. 

 

n = 2t*21 = 3t*14 = 6t*7 = 7t*6 = 21t*2 so all the ten numbers

2t + 21, 2t - 21, 3t + 14, 3t - 14, 6t + 7, 6t - 7, 21t + 2, 21t - 2 are primes and

except 2t - 21 all of them are greater than 11, since t is odd(n is square free)

2t - 21 doesn't equal to 11.

 

11 doesn't divide 3t +14  so t isn't of the form 11r - 1.

11 doesn't divide 3t - 14  so t isn't of the form 11r + 1.

11 doesn't divide 21t - 2  so t isn't of the form 11r - 2.

11 doesn't divide 21t + 2  so t isn't of the form 11r + 2.

11 doesn't divide 6t + 7  so t isn't of the form 11r - 3.

11 doesn't divide 6t - 7  so t isn't of the form 11r + 3.

11 doesn't divide 7t - 6  so t isn't of the form 11r - 4.

11 doesn't divide 7t + 6  so t isn't of the form 11r + 4.

11 doesn't divide 2t + 21 so t isn't of the form 11r - 5.

11 doesn't divide 2t - 21 so t isn't of the form 11r + 5.

 

Hence t is of the form 11r and n = 2*3*7*11*r = 462r.

 

***********

I am sure that the largest term of the sequence is 462.

 

Argument:

 

If n is a term greater than 462 then n = 2*3*7*11*r = 462r,  where r>1, r is square

free and gcd(r, 2*3*7*11) = 1.

 

Since n = 1*462r = 2*231r = 3*154r = 6*77r = 7*66r = 11*42r = 21*22r = 22*21r

= 42*11r = 66*7r = 77*6r = 154*3r  = 231*2r = 462*r

according to the definition all the following numbers are none-composite numbers.

 

462r - 1, 462r + 1, 231r - 2, 231r + 2, 154r - 3, 154r + 3, 77r - 6, 77r + 6,  66r - 7

66r + 7, 42r - 11, 42r + 11, 22r - 21, 22r + 21, 21r - 22, 21r + 22, |11r - 42|, 11r + 42, |7r - 66|, 7r + 66, |6r - 77|, 6r + 77, |3r - 154|, 3r + 154, |2r - 231|, 2r + 231, |r - 462|,

r + 462.

Note that the set of integer solutions of the equations |6r - 77| = 1, |3r-154| = 1,

|2r - 231| & |r - 462| are respectively {13}, {51}, {160, 161} & {461, 463}  and 3 | 51,

2 | 160, 7 | 161 & 11 | 463. Since n is square free and for  r = 13 & 461,n isn't a term

of the sequence , we deduce that all the above 28 numbers are greater than 1.

So they are primes.

And It seems there is no a number r greater than one with the properties r is square

free, gcd(r, 2*3*7*11) = 1 and all the 28 above numbers are primes.

***

Fred Schneider added on May 25, 2006:

To add to Farideh's answer, if 2,3, 7 and 11 divide the number, 19 must either divide the number or the number must be of the form
x=n(n-19) so that there is exactly one x/d-d that equals 19. To have a shot at this, we must find a number n=19a+b such that b is not already a modulus that would result in a solution to 19 | x/d +/- d for some d where is a divisor of 2*3*7*11.

The unique residues from n(n-19) are simply the quadratic residues of 19:

1, 4, 9, 16, 6, 17, 11 ,7 and 5

Respectively, the d which result in x/d-d being a multiple of 19 are as follows:
1, 2, 3, 42, 14, 6, 7, 11, 66

Picking the largest of these factors, neither n=66*47 or 66*85 is a potential solution so 19 must be a factor of the number.

So now the solution must be some multiple of 2*3*7*11*19=8778. We run into a bigger dilemna now. There are 3 new primes that must be "part"
of the solution. Crunching the moduli through the expanded set of divisors, now 23, 31, and 47 must all be factors of the solution or satisfy the relation

8778x = n(n-p) where p is 23 or 31 or 47.

Of course with each prime added into the mix, more primes p are tacked on as having to be either a factor or forces the number to be of the form n(n-p).

Note: If 23,31 and 47 are factors of the solution, the following primes must be part of the solution:

43,59,67,71,79,83,103,107,131,151,167,191

Clearly, this is vicious cycle and there are no other solutions.
 

Then I asked him: "Your approach can explains why exist 5 solutions before the vicious
cycle appears?"

I should have been a little clearer. There are solutions before the "vicious cycle" starts because some of the n/d +/-d are the same small primes themselves.

Some background:

If n-1 and n+1 are prime, n must be an even number (2 is a solution) If n-1 and n+1 are prime, we also know that n can't be of the form
3x+/-1 because then one of its neighbors must be prime. So, n is a
multiple of 6 (6 is a solution)

If a number is a multiple of 2*3 (and GREATER than 6) it must also be a multiple of 7 based on set of divisors' modulos (unless the number is of the form n=x(x-7) which wasn't ruled out in the first proof.
That is a possibility and n=30=10*(10-7) is the only solution. That is because all numbers n=7x+b (where b=1 through 6) would result in one of n+/-1 or n/2 +/- 2 or n/3 +/-3 being a multiple of 7. The n/3
- 3 = 7 => n=30 is the highest number where one of these early n/d
+/-d values could be 7 itself.

42=2*3*7 is the only solution.

If a number is a multiple of 2*3*7=42 (and GREATER than 42) it must also be a multiple of 11 based on set of divisors' modulos. It was ruled out in the last mail that n=x(x-11) was a possible solution.
462=2*3*7*11 is the only solution.

If a number is a multiple of 2*3*7*11=462 (and GREATER than 462) it must also be a multiple of 19 for the same reason.
I verified that 8778= 2*3*7*11*19 is not a solution and hence the vicious cycle begins.
 

***

 

---