Problems & Puzzles: Puzzles
|
Problems & Puzzles: Puzzles
From Feb 28 to March 6, 2026, contributions came from Rahid Zaman, Gennady Gusev, *** Rahid wrote:
The answer is yes. Here's a proof:
---
If N is odd, then (N+30) is odd.
The biggest prime factor of an odd number is an odd prime. So after one move, the sequence is now on odd primes.
---
Suppose the current value is an odd prime "p".
a. If (p+30) is prime, then A(p) is just (p+30). b. If (p+30) is composite, then since it's odd, it must have a prime factor of at least 3. So A(p) is at most (p+30)/3.
---
Suppose you’re in case (a), so the terms are all prime and look like p,
p+30, p+60, …, p+30k. First, let's say you have seven of
these, so all the way from p to p+180.
Now go mod 7.
Since 30 ≡ 2 (mod 7), the residues are p (mod 7), p+2 (mod 7), p+4 (mod 7), ... Look at the first 7 of them (k = 0 to 6): p+2k (mod 7) gives p, p+2, p+4, p+6, p+8, p+10, p+12 (mod 7), i.e. p, p+2, p+4, p+6, p+1, p+3, p+5 (mod 7). That’s all 7 residue classes exactly once, so realistically, one of those terms is divisible by 7. But in this run every term is prime, and the only prime divisible by 7 is 7 itself. So that “divisible by 7” term must actually equal 7. So if p isn't 7, you can only go up to a maximum of 5 more terms (+150) before hitting a composite number (and the next drop). ---
Take the peak value P (right before a drop).
After the drop, it's at most (P+30)/3
Then you get at most +150 of climbing before the next drop If you set the inequality (P+30)/3 + 150 < P, you get P > 240 So if P > 240, then (P+30)/3 + 150 is always less than P, so peaks strictly decrease.
For example with P = 509:
359 -> 389 -> 419 -> 449 -> 479 -> 509 -> 11
Even if 509's largest factor was 3, it'd still push it below 359, so it
inevitably gets lower and lower.
That means every attempt eventually gets down to the zone <= 240.
---
Then you just run the code for all P < 240, which you already did (and I
double-checked on my PC), and there's the proof.
*** Gennady wrote:
I propose such a proof.
Let N be the starting number.
Then in Arithmetic Progression N + 30*k , k=0..6 will be at least one
composite number,
because according to the difference 30=2*3*5 there can be no more than
6 primes.
Let the composite be the maximum possible N+180. If we take 3 as its
smallest divisor,
then its largest divisor (GPD) <= (N+180)/3.
Find for which N GPD(N+180) < N. Solving the inequality (N+180)/3 < N,
we get the answer: N>90.
In any chain starting with N>90, we will sometime get GPD < 90.
But all the odd ones < 90 are checked and give cycle-7.
So we always come to the cycle including the integer 7.
***
|
|||
|
|||
|
|||
