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.
Subquestions:
***
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=NM. 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 subquestion, 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?".
His answer was:
"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?
His answer (7/10/01) was:
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!".
But he added:
"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*Ma3*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*Ma3*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."
***
