[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/
More information about the SeqFan
mailing list