[seqfan] Re: Formulas for two sequences, A060574 and A067498 ?

[Antti Karttunen]

On 3/29/22, M. F. Hasler <oeis at hasler.fr> wrote:
> Yes, for the tower of Hanoi there is a very simple algorithm that easily
> translates to a formula :
> on the first, third, fifth,... move, move the smallest disc to the next
> peg,
> so the smallest disc is on peg (ceil(n/2) mod 3) after the n-th move,
> which yields departure and arrival peg number for any of these moves.
> On the 2nd, 4th, 6th... move, make the only possible move with a disc other
> than the smallest one.
> You can check that for moves numbered
> A108269 <https://oeis.org/A108269> Numbers of the form (2*m - 1)*4^k where
> m >= 1, k >= 1.this corresponds to the move (a -> a+1 (mod 3)) where a =
> floor(n/2+1) mod 3 is the peg just "after" the one on which you just put
> the smallest disc,
> for the other even moves,  with numbers A036554
> <https://oeis.org/A036554> (binary
> representation ends in an odd number of zeros),
> it's the "reverse" move: (a+1 (mod 3) -> a).
>
> For the "number of reflections" sequence, i don't understand the given
> definition, i will have a look at the sequence.

It would help if we had an access to the reference:

M.O. van Deventer in The Mathemagician and the Pied Puzzler edited by
E. Berlekamp and T. Rodgers, AKPeters Publishers, pp. 245-251.

Does any on SeqFan has this book at their disposal?

The mined LODA-assembly program:
https://github.com/loda-lang/loda-programs/blob/main/oeis/067/A067498.asm

refers to A340081(n) = gcd(n-1, A003958(n)), where A003958 is: If n =
Product p(k)^e(k) then a(n) = Product (p(k)-1)^e(k).

When the LODA-assembly is converted to PARI (taking heed of differing
starting offsets, for LODA-programs it is always 0), we get this:

A003958(n) = if(1==n,n,my(f=factor(n)); for(i=1,#f~,f[i,1]--); factorback(f));
A067498maybe(n) = 1+(2*((((n-1)^2)+gcd(n-1,A003958(n)))\2));

I.e., the tentative formula for A067498 would be
   a(n) = 1 + clear_the_lsb_of[ ((n-1)^2) + gcd(n-1,A003958(n)) ],
but with only seventeen known terms, this could well be a spurious match.

BTW, here's a similarly mined program for the Tower of Hanoi related sequence:
https://github.com/loda-lang/loda-programs/blob/main/oeis/060/A060574.asm
involving a period 6 (repeat [0, 1, 1, 1, 1, 0]) sequence A131719.

(And my thanks to all seqfans who have put effort to find a formula
for A060574.)


Best regards,

Antti


>
> - Maximilian
>
> *(PARI/GP) <http://pari.math.u-bordeaux.fr/gp.html>*
> *Hanoi(n,p=[[]|n<-[1..3]])={p[1]=[1..n]; vector(2^n-1, n,** my(m = if(
> bittest(n,0), [n\2%3, (n\2+1)%3]*
> *, my(a = (n\2+1)%3, b = (a+1)%3); if(** !p[b+1] ||
> (#p[a+1]&&p[a+1][1]<p[b+1][1])**,* *[a,b], **[b,a])/*if*/*
>  *)/*if*/ )/*my*/;** p[m[2]+1] = concat( p[m[1]+1][1],
> p[m[2]+1]); p[m[1]+1] = p[m[1]+1] [^1]; m**)}*
>
>
> On Mon, Mar 28, 2022, 08:06 Antti Karttunen <antti.karttunen at gmail.com>
> wrote:
>
>> Cheers,
>>
>> Does anybody know formulas for these two sequences?
>>
>> https://oeis.org/A060574
>> Tower of Hanoi: using the optimal way to move an even number of disks
>> from peg 0 to peg 2 or an odd number from peg 0 to peg 1, a(n) is the
>> smallest disk on peg 1 after n moves (or 0 if there are no disks on
>> peg 1).
>>
>> https://oeis.org/A067498
>> Maximum number of reflections for a ray of light which reflects at n
>> points (reflecting more than once at most or all points).
>>
>> These recently appeared among the newly mined LODA-programs (see
>> https://github.com/loda-lang/ ), but at least for the latter there are
>> so few terms present that it is highly likely a case of strong law of
>> small numbers.
>>
>>
>> Best regards,
>>
>> Antti
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>