# [seqfan] Re: Can we always reach a power of 2 with this formula?

Jeffrey Shallit shallit at uwaterloo.ca
Sun Dec 26 22:16:22 CET 2021

```You want to show there is an a(n) such that 2^n + a(n)n(n+1) = 2^{n+b}
(*) for some b.

In other words, you want to find b such that 2^{n+b} - 2^n == 0 (mod
n(n+1)).

Rewrite as 2^n(2^b - 1) == 0 (mod n(n+1)).

Write n(n+1) = r*2^s, where r is odd.

So we want 2^n(2^b - 1) == 0 (mod r*2^s).

Now s is at most log_2(n(n+1)), and we need n >= s.
So we want n >= log_2 (n(n+1)), which is true for all n>4.  But you
already found solutions for these n<=4.  So assume n>5.

It remains to choose b such that 2^b - 1 == 0 (mod r), where r is odd.
We can do this easily by choosing b = phi(r), where phi is the Euler-phi
function.    Smaller b is of course possible.

This shows that b can always be chosen, so a(n) always exists.  You can
find the least such a(n) just by testing b = 1, 2, ... until you find
2^b == 1 (mod r), where r is is the odd part of n(n+1) and computing
a(n) from (*).  More efficient methods are possible, of course.

Hope that helps.

Here are the first few values of your a(n):

1              1
2              2
3              2
4             12
5             16
6             96
7             16
8            224
9          23296
10        9761280
11          15872
12         107520
13         184320
14         319488
15           2048
16          61440
17     7186350080
18      200933376
19 94812623732736
20       10223616
21  4874025566208

On 2021-12-25 4:16 p.m., Ali Sada via SeqFan wrote:
> Hi everyone,
>
> a(n) is the least positive integer such that 2^n + a(n)*A002378(n) equals to a power of 2.
>
> 2^1 + 1*2 = 4,  a(1) = 1
> 2^2 + 2*6 = 16,   a(2) = 2
> 2^3 + 2*12 = 32,   a(3) = 2
> 2^4 + 8*20 = 256,  a(4) = 8
> 2^5 + 16*30 = 512, a(5) = 16
> 2^6 + 96*42 = 4096, a(6) = 96
> 2^7 + 16*56 = 1024, a(7) = 16
>
> Can we prove that we can always find a value for a(n)?
> I would like to add this sequence to the OEIS and I would really appreciate it if someone could calculate the necessary terms if possible.
>
> Best,
>
> Ali
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/

```