0

Given some $n$, is it possible to select $k_i$ such that the following is true?

$$ 3^n2^{k_0} + 3^n2^{k_1}+ 3^n2^{k_{2}} + 3^n2^{k_3} + ... + 3^n2^{k_i} = 2^m - 1 $$

for $n=1$ it's trivial, for $n=2$ it's $$ 9 + 9 \times 2 + 9 * 4 = 64 - 1 $$ for $n=3$ $$ k_i = [0, 2,3,5,6, 7, 8, 10, 13] $$ and $n=4$: $$ k_i = [0, 1, 2, 3, 6, 8, 9, 10, 12, 13, 15, 17, 18, 21, 22, 23, 24, 25, 26, 31, 32, 34, 38, 41, 43, 46, 47] $$ where the above was found using brute force in python. I've found values for $n$ up to 8 with about 2000 $k$.

Is this true for all n (I think yes)? And how would I show this?

Haris
  • 3,409
alwaysmpe
  • 111
  • 4
  • 2
    All you need is for $2^m-1$ to be divisible by $3^n$, and you can do that for arbitrary $n$. I think you get a multiple of $3^n$ for $m=2\times3^{n-1}$. – Gerry Myerson Feb 23 '24 at 03:20

1 Answers1

1

$k=\sum2^{k_i}$ can represent any number (uk the entire point of binary numbers) where all $k_i$ are obviously distinct

So your question simplifies to $$ 3^nk=2^m-1 $$

Now it is clear there are multiple solutions but proving it exists for every n is trivial

From Euler's theorem $$ 2^{\phi(3^n)}\equiv1 \bmod(3^n) $$ Where $\phi(n)$ is Euler's totient function

In other words $$ 2^{\phi(3^n)}-1=3^nk $$

We can write $\phi(3^n)=2\cdot3^{n-1}$

Here is where the multiple solutions come in we have no guarantee that the minimum exponent that satisfies this is $\phi(3^n)$ but we do know it is a solution

Now we can work back to find everything else

$$ m=2m'=2\cdot3^{n-1}\\ \{k_r\}_i=\{\text{The powers in binary representation of k}\}\\ i=\lfloor\log_2(k)\rfloor $$

Note:

You can see it overshoots for $n=3$

And the number of k's grows roughly exponentially

RandomGuy
  • 1,349