Problems & Puzzles: Conjectures

Conjecture 25. sopf(n) = sopf(n+k)

Let's define:

sopf(n) = "sum of prime factors of the value n, without repetition"

Examples:

sopf(714)=sopf(2x3x7x17) = 2+3+7+17

sopf(81) = sopf(3x3x3x3) = 3

Jason Earls sent to these pages the following conjecture

For any k value there is always at least one n value such that: sopf(n)=sopf(n+k)

Questions:

1) Can you prove the Jason's conjecture or give a counterexample?
2) Can you redo the exercise changing the definition of the
sopf(n) function to "sum of prime factors of the value n, with repetition"?

_______
Note: Another puzzle related with this issue is the Puzzle 97 in these pages.

Solution

Jud McCranie has verified (30/9/01) both conjectures for k<1,936,267

***

He also has produce the following table on my request:

 Table: k vs n* k n* n*+k sopf 1 5 6 5 3 7 10 7 5 114 119 24 21 209 230 30 25 493 518 46 35 516 551 48 55 855 910 27 185 1194 1379 204 265 1274 1539 22 563 2815 3378 568 569 2834 3403 124 733 3180 3913 63 3350 3186 6536 64 3469 5225 8694 35 6010 6010 12020 608 6779 8056 14835 74 10689 8357 19046 198 11143 8954 20097 50 14505 11439 25944 75 18016 13684 31700 324 30561 14599 45160 1136 31588 15748 47336 160 37757 17298 55055 36 59611 17384 76995 96 65816 17784 83600 37 67106 20940 88046 359 75904 25886 101790 52 118361 36223 154584 137 214379 36938 251317 109 241564 41796 283360 48 255196 53725 308921 319 414221 64855 479076 138 648152 67942 716094 243 703812 69167 772979 289 881848 72468 954316 77

n* is the minimal n value such that sopf(n*)=sopf(n*+k) for a given k, showing only these entries where n* increases respect the previous entry.

Sub-questions:

• Is there an upper limit for n*

• Would it happen again that n*>k?

***

Chris Nash almost solves (1/9/01) completely this conjectures, but at least he shows where to find for the complete solution.

"I was very interested in Jud McCranie's experimental data for the "sopf(n)=sopf(n+k)" conjecture, and I thought it was about time I presented my theoretical results to go with them. So far I have managed to prove:

For *a large proportion* of k values there is always at least one n value such that sopf(n)=sopf(n+k).

Of course, I need to say more about *a large proportion*. I expect, that with the data Jud has generated, we may very easily be able to construct a proof. Here is the key part of the proof.

Suppose there are two integers M,N>1 such that sopf(M)=sopf(N). Then evidently that demonstrates a solution for k=N-M. Choose any integer Q> 1 such that any of Q's prime factors are factors either of *both* M and N, or *neither* M and N. Then Q.M, Q.N, gives a solution for Q.k.

Now, to construct the proof, we need to construct a table of sopf(n).

We will find some interesting results on the way. We may write a little program that generates each sopf(n), looks through all previous values of n to find an equal value, and applies the lemma above to generate an interesting 'rule'.

Here are some examples of rules we can generate.

sopf(2)=sopf(4).

Let Q be *any* integer. Then sopf(2Q)=sopf(4Q), and so we have a solution for k=2Q with n=2Q (In other words, in Jud's table, n*<=k for even k at least). This covers all even values of k.

sopf(5)=sopf(6).

Let Q be an integer with no factors 2, 3, or 5. Then sopf(5Q)=sopf(6Q) and so we have a solution for k=Q.

At this point then the only k values that remain are odd multiples of 3 or 5. (I think this covers over 76% of the possible k).

We may continue for other rules. For example sopf(7)=sopf(10). *But* often we can improve the rule we find. For instance sopf(7)=sopf(10)=sopf(49)=sopf(50). Let Q be an integer with no factors 2, 5, or 7. Then sopf(49Q)=sopf(50Q) gives a solution for k=Q, and sopf(7Q)=sopf(10Q) gives a solution for k=3Q.

Now the only k remaining unsolved have factors of 5 *or* factors of * both* 3 and 7. Now it is interesting to look at Jud's tables - 5 and 21 are in fact the next *difficult* values of k. This is not a coincidence. Let us look at k a multiple of 5. Jud's table tells us sopf(114Q)=sopf(119Q) is a solution for k=5Q, *provided* Q has no common factors with 114 or 119. In other words, we have solved for multiples of 5 * provided* they have no factors 2, 3, 7, 17, 19. Even more k values are covered.

By identifying more pairs such that sopf(M)=sopf(N), we can cover more and more values of k. Perhaps if Jud has already generated the table of sopf's, he might just be able to finish the proof and find a set of rules that 'cover' all the k... I am sure *almost all* k will fall to this method! Perhaps even there are better rules to support Jud's new sub-question, that n*<=k....

As a quick note, the "rule generator" I mention above works in question 2) as well, the same lemma holds even if sopf() is defined *with* repetition.

***

One day after Chris sent his solution I asked him: "The set of rules for a complete solution of this conjecture is a finite set?".

"This I do not know yet... but I think the answer is yes. There seem to be two different kinds of rules. For some, M and N have no common factors and so sopf(QM)=sopf(QN) *only* for certain values of Q. But there are other rules (such as 2,4) for which *any* value of Q will work. So perhaps what happens is, with many of the first rule all that remains is "k is solved except for multiples of ????". Then we find the second kind of rule for ????...."

***

Suddenly, the 5/10/01, the answer come from an unexpected place. Mr Dean Hickerson wrote:

On your web page at Conjecture 25 you discuss Jason Earls's conjecture that for any k there is at least one n such that sopf(n)=sopf(n+k). You claim that Chris Nash's method will yield a complete solution. Here's a proof that it won't:

Suppose we have a finite set of pairs (Mi, Ni) which 'covers' all odd numbers. I.e. for each index i, sopf(Mi) = sopf(Ni) and for every positive odd number k there's an index i and a positive integer Q such that Q (Ni - Mi) = k and every prime factor of Q is a factor of both Mi and Ni or of neither Mi nor Ni.

Let k be the product of all odd primes which divide some Mi or Ni, and suppose that k is covered by the pair (Mi, Ni); thus Q (Ni - Mi) = k for some Q, all of whose prime factors divide either both or neither of Mi and Ni. Since k is odd, one of Mi and Ni is even and the other is odd. Also, there's some odd prime p which divides exactly one of Mi or Ni; otherwise sopf of the even one would be 2 more than sopf of the odd one.

By definition of k, p divides k. Since p doesn't divide Ni - Mi, p must divide Q. But every prime factor of Q is a factor of either both or neither of Mi and Ni, so we have a contradiction. Hence our finite set of pairs doesn't cover all odd numbers.

***

My immediate response to Dean was something like this:

Does your proof means that the Conjecture is false or only that the set of rules from the Chris's approach is necessarily infinite?

It doesn't mean that Jason's conjecture is false, just that Nash's original method isn't sufficient to prove it.

***

The Chris's comment about the Dean's proof was: "That's a great proof, Euclid would love it!".

"Indeed, with the existing set of rules, there most certainly is *not* a finite set. We do in fact need a further, more general rule....

Let sopf(M)=sopf(N). Then there are four types of primes:

1) primes that divide both M and N
2) primes that divide M, but not N
3) primes that divide N, but not M
4) primes that divide neither M nor N.

Create four integers a1,a2,a3,a4 such that all the prime factors of ai are in the set i.

Then sopf(a1*a2*a4*M)=sopf(a1*a3*a4*N)

giving a solution for k=a1*a4*(a2*M-a3*N)

That *might* be enough to fix it... but still I don't know exactly how. One way is to find large solutions M and N, for instance M=2*3*11*13, N=5*7*17 and so there are many possible ways to choose a2 and a3 to get many different values of a2*M-a3*N.... but still, no further progress!

***

Mr. Dean Hickerson wrote (10/10/01) the following about the Nash's second approach:

"The new proposal doesn't work either. Essentially the same proof as before shows that no finite set of pairs will work:

As before, let k be the product of all odd primes which divide some M_i or N_i, and suppose that k is covered by the pair (M_i, N_i); i.e. we have k=a1*a4*(a2*M_i - a3*N_i) where a1, a2, a3, and a4 are as described in Nash's proposal. As before, there's an odd prime p which divides exactly one of M_i or N_i. If p divides M_i, then p doesn't divide either a3 or N_i, so p doesn't divide a2*M_i - a3*N_i. Similarly, if p divides N_i, then p doesn't divide either a2 or M_i, so p doesn't divide a2*M_i - a3*N_i.

And p obviously doesn't divide either a1 or a4, so p doesn't divide k, contradicting the definition of k."

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.