Conjecture regarding A383977 (merge positions when Fibonacci-sorting)

[Joerg Arndt]

Had to recycle my first submission in two years because it is certainly
a duplicate of A383977. Can anybody understand the Python program and
compare it to what I gave in my paper (section 3: Loopless computation
of the successor for non-adjacent forms)?
https://oeis.org/draft/A383977
My C++ code: https://jjj.de/fxt/demo/seq/#A383977

Alternatively the following has been suggested:
"Michael S. Branicky: Maybe Jeffrey Shallit or one of his students can prove using Walnut?"

Best regards,  jj

[Jeffrey Shallit]

Unfortunately computing 1,000,000 suggests the sequence is not Fibonacci-synchronized, so Walnut won't be of any help (probably).

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/d9f912f6-11f8-4614-8f25-020fcfba9f62%40th-nuernberg.de.

[Kevin Ryde]

Joerg Arndt <joerg...@th-nuernberg.de> writes:
>
> A383977. Can anybody understand the Python program andcompare it

Just on the program, it does what your table looks like
and what the formula says:

In Zeckendorf base, at most significant 1 digit,
apply a numerical +1 with wrap-around in the digits below.
Seek the next lower 1 digit in the modified value
and repeat, until no more 1 digits.

In the code, f[0] is a(1) so the copying loop begins j=0
for the +1. The extra f.append() is the wrap-around case.

I believe equivalent in binary is A108918,
ie. below each 1 bit apply +1 with wrap-around.


\\ return i with F(i) <= n < F(i+1)
Zeckendorf_highpos(n) =
{
for(i=1,oo,
if(n < fibonacci(i+1), return(i)));
}

A383977(n) =
{
my(result=0);
while(n,
my(i=Zeckendorf_highpos(n),
F=fibonacci(i));
result += F;
n -= F;
n = (n+1) % fibonacci(i-1));
result;
}

[Ruud H.G. van Tol]

Alternative PARI code, following your table example in A383977:

atleast(nn)= {
  my(p=0, r=List(), s, t);
  while( #r < nn
  , s= 1<<p;
    t= s>>1;
    for(i=1,#r
    , r[i]<t || break;
      listput(~r, s+r[i])
    );
    listput(~r, s);
    p++
  );
  Vec(r)
}

? atleast(20)
%1 = [1, 2, 5, 4, 9, 10, 8, 17, 18, 21, 20, 16, 33, 34, 37, 36, 41, 42,
40, 32]

? my(v=atleast(20), s=Set(v)); [ setsearch(s,t) |t<-v]
%2 = [1, 2, 4, 3, 6, 7, 5, 9, 10, 12, 11, 8, 14, 15, 17, 16, 19, 20, 18, 13]

-- Ruud