2
$\begingroup$

Let $f(n)$ be A000045(n), i.e., Fibonacci numbers: $f(n)=f(n-1)+f(n-2)$ for $n>1$ with $f(0)=0$ and $f(1)=1$.

Let $g(n)$ be A072649, i.e., $n$ occurs $f(n)$ times. The sequence begins with $$1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7$$ Here we also consider that $g(0)=0$.

Let $$h(n)=n-f(g(n)+1)$$ Claude Chaunier pointed out in his comment that

From OEIS we see $f(g(n)+1)$ is the highest Fibonacci number $\leqslant n$ and $h(n)$ is how far $n$ is from it.

So the binary analogs of these functions are: powers of $2$ for $f(n)$, $\left\lfloor\log_2 n\right\rfloor$ for $g(n)$ and $n$ without the most significant bit for $h(n)$.

Let $a(n)$ be an integer sequence such that $a(0)=0$, $a(n)=n$ if $n$ is Fibonacci number, otherwise $$a(n)=n - f(g(h(n)-1)) + [g(n)\operatorname{mod}2 = g(h(n)-1)\operatorname{mod}2]\cdot f(g(n)-2)$$ I conjecture that $a(n)$ is a permutation of the nonnegative integers.

Here is the PARI prog to verify this conjecture:

g(n)=local(m); if(n<1, 0, m=0; until(fibonacci(m)>n, m++); m-2) \\ from A072649
a(n) = if(n>0, my(A=g(n), B=n-fibonacci(g(n)+1), C=g(B-1)); n + if(B>0, - fibonacci(C) + if(A%2==C%2, fibonacci(A-2))))
test(n) = my(A=0); while(!(a(A)==n), A++); A

Is there a way to prove it? Is there a binary analog of this permutation?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ You might consider adding some deciphering comments. From OEIS we see $f(g(n)+1)$ is the highest Fibonnaci number $\le n$ and $h(n)$ is how far $n$ is from it. Then $g(h(n)-1)$ is $\dots$ I don't know yet. It involves $g(-1)=0$ according to your GP/PARI code output. $\endgroup$
    – Claude Chaunier
    Commented Apr 3, 2023 at 11:00
  • 2
    $\begingroup$ It looks like some obfuscating code of a permutation someone deliberately crafted. Not trivial but nothing mathematically unexpected either. You must tell us I am wrong to expect anybody here have a look at it. $\endgroup$
    – Claude Chaunier
    Commented Apr 3, 2023 at 11:11
  • 2
    $\begingroup$ What does the expression in square brackets denote? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Apr 3, 2023 at 12:31
  • 1
    $\begingroup$ A challenge :D There is a unique way to run it backwards, $f(n)=f(n+2)-f(n+1)$, so that $f(-n)=-(-1)^nf(n)$. Note that in particular $f(1-2n)=f(2n-1)$, which prevents you from extending your map to a permutation of all integers. Nevertheless, what kind of map would you get? Maybe you can start with some other recurrence to still obtain a permutation? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Apr 13, 2023 at 8:55
  • 1
    $\begingroup$ No, sorry for being unclear. I wanted to say that maybe there is another recurrence, possibly more complicated, $f(n)=c_1f(n-1)+...+c_kf(n-k)$ which, upon extrapolating to negative integers produces, following extrapolation of the analog of your construction for this recurrence, would give a permutation of all integers. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Apr 13, 2023 at 9:45

1 Answer 1

Reset to default
1
$\begingroup$

For an illustration, here is the graph of $a(n)-n$ for $n$ up to the 32nd Fibonacci number

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .