1
$\begingroup$

Let $$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$ $$f(n)=n-2^{\ell(n)}$$ $$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$ $$\operatorname{wt}(2n+1)=\operatorname{wt}(n)+1, \operatorname{wt}(2n)=\operatorname{wt}(n), \operatorname{wt}(0)=0$$ Here $f(n)$ is the distance to largest power of $2$ less than or equal to $n$, $T(n,k)$ is the $(k+1)$-th bit from the right side in the binary representation of $n$ and $\operatorname{wt}(n)$ is the binary weight of $n$.

Let $a(n)$ be a sequence of positive integers such that $$a(n)=(1+\operatorname{wt}(n))a\left(\left\lfloor\frac{n}{2}\right\rfloor\right), a(0)=1$$ Here $a(n)$ is A284005.

I conjecture that there exist recurrence such that for $n>1$ $$a(n)=2a(f(n))+\sum\limits_{k=0}^{\ell(n)-1} a(f(n) + 2^{k}(1 - T(n,k)))$$ There are no counterexamples up to $10^6$.

Is there a way to prove it?

$\endgroup$
3
  • 1
    $\begingroup$ How far have you gone in checking this supposed recurrence numerically? $\endgroup$
    – Somos
    Apr 18, 2023 at 19:34
  • $\begingroup$ @Somos, thank you for comment! I usually check up to $10^6$. $\endgroup$ Apr 19, 2023 at 7:02
  • 1
    $\begingroup$ Since $T(n, \ell(n)) = 1$ the conjecture could equivalently be written as $$a(n) \stackrel?= a(f(n))+\sum\limits_{k=0}^{\ell(n)} a(f(n) + 2^{k}(1 - T(n,k)))$$ $\endgroup$ Apr 19, 2023 at 10:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.