[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