Conjecture in A103200 settled

[Rainer Rosenthal]

The first sentence in the comments of
http://www.research.att.com/~njas/sequences/A103200
says:

       The authors ask for a proof that
       a(n) is always an integer.

But
1. there is only one author (njas)
   and
2. according to the recursion formula (2005)
   a(n) = 8*a(n-2)-a(n-4)+3 with integer starting
   values, a(n) is indeed always an integer.

I see Ralf Stephan as a contributor (18th May 2007), so
maybe he thought the text was OK?

My question this morning in sci.math was answered by
Jan Haugland immediately and surprisingly short. I
think he was right.

I could change the comments but I hesitate because of
this mystical hint "The original version of this
question was ..."

Maybe the author would like to clarify this himself?

Many greetings to the author Neill Sloane,
Rainer Rosenthal
r.rosenthal at web.de




"Stefan Steinerberger" <stefan.steinerberger at gmail.com> wrote:
:> Is the sequence of positive integers infinite, where m is included in the
:> sequence if and only if: the mth integer from among those positive
:> integers which are coprime to (m+1) = the (m+1)th integer from
:> among those positive integers which are coprime to m ?
:> This sequence begins 3, 15,...
:
:Assuming my programming isn't faulty the sequence should
:go like this: 3, 15, 104, 164, 255, 2625, 2834,...
:So far every number also appears in A001274 although there
:are some numbers (like 194) in A001274 which aren't in the
:sequence.
:
:If it could be shown that this sequence is a subset of A001274,
:then its infinitude will be hard to prove since it is an open problem
:whether A001274 is indeed infinite.

Just to make things easier to talk about, let me define C(x, y) as the
y'th positive integer comprime to x, so that we are searching for

I confirm those findings; the full list of m, C(m,m+1) for all
m <= 250000 goes like:
3: 5
15: 29
104: 227
164: 337
255: 509
2625: 5743
2834: 6197
11715: 24509
18315: 38827
48704: 97537
49215: 98557
64004: 128017
65535: 131069
73124: 148531
131144: 287107
215775: 475481
and also:
4294967295=2^32-1: 8589934589=2^33-3

These are indeed all elements of A001274. However, I think it remains
possible that elements of this sequence will have phi(m) != phi(m+1),
though the two values will need to be close.

It is interesting to see that F_n-2 = 2^(2^n)-1 appears in the sequence
for n in (1, 2, 3, 4, 5), C(m,m+1) being 2^(2^n+1)-3 in each case.
F_6, F_7, F_8 and F_9 are not in the sequence, however.

My approach to calculating these is to pick a trial candidate for C(x, y)
as 2x-1 = C(x, 2 phi(x)). I start with the even element of {m, m+1}, and
if I find that the candidate is too high, I walk downwards to find it,
then check the odd element, shortcircuiting as I go. If I find the
candidate for the even element is too low, I check the odd element first -
failing to do this makes it much slower, since in some cases the candidate
is *much* too low. This approach took 15 minutes to check to 250000.

Hugo