[seqfan] Re: Davide Rotondo's conjecture

[israel at math.ubc.ca]

This is simply a consequence of the fact that if x < y, 0 <= pi(y) - pi(x) 
<= y - x and the inequality on the right is strict if y-x > 1 except for 
the case of 1 and 3.

Thus we start with b(0) - b(1) = pi(n). While |b(i) - b(i+1)| > 2 
we get |b(i+1) - b(i+2)| = |pi(b(i+1)) - pi(b(i+2))| < |b(i) - b(i+1)|.
Eventually we must either reach |b(j+1) - b(j)| = 0 or
|b(j+1) - b(j)| = 1.  
If it's 0, i.e. b(j+1) = b(j), then clearly b(k) = b(j)
for all k > j.  
If b(j+1) = b(j) + 1 = n - pi(b(j)), then
 b(j+2) = n - pi(b(j)+1) = b(j+1) or b(j+1)-1.
If b(j+1) = b(j) - 1, then
 b(j+2) = n - pi(b(j)-1) = b(j+1) or b(j+1)+1.
Thus from this point on we either get a 2-cycle or a 1-cycle.

Cheers,
Robert

                



On Mar 26 2024, Neil Sloane wrote:

>Dear Sequence Fans,
>
>On March 23 2024, Davide Rotondo sent me an email with the following
>interesting conjecture.
>
>(I've simplified it a bit.)
>
>For a positive integer n, define a sequence b by b(0) = n; b(i) = n -
>pi(b(i-1)) for i >= 1,
>
>where pi(x) = number of primes <= x.
>
>The conjecture is that after some initial terms, b becomes periodic with
>period length 1 or 2,
>
> and the n for which the period is 2 are 3 together with A095116, that is,
>2, 3, 4, 7, 10, 15, 18, 23, 26, 31, 38, 41, 48, ...
>
>I've checked a few thousand terms and it seems to be true. Here is a random
>example: for n = 2954, the b sequence is 2954, 2529, 2585, 2578, 2579,
>2578, 2579, ..., with period 2.
>
>There is probably a simple proof, but I don't have time to work on it.
>
>I'm going to add it as a comment to A095116, and if anyone has a proof, I
>will add it there.
>
>
>Best regards
>Neil
>
>Neil J. A. Sloane, Chairman, OEIS Foundation.
>Also Visiting Scientist, Math. Dept., Rutgers University,
>Email: njasloane at gmail.com
>
>--
>Seqfan Mailing list - http://list.seqfan.eu/
>
>