Interesting Finding: Solving f(a_0, n_0) for All Integers m

[Werg22]

I had a little insight, and I'm curious whether or not it's true.

What I conjecture:

Say we have a set of functions S = {f(a, n) = b_n * a^n + b_n-1 * a^n-1 + ... + b_0} where a and n must be both natural numbers, and b must belong to {-1, 0, 1}. Then for fixed a = a_0 and n = n_0, we have that for every integer m from 0 to s = 1 + a_0 + a_0 ^2 + ... + a_0 ^n_0, there are values of b satisfying f(a_0, n_0) = m. For example, choosing a = 2 and n = 2, we have the integers 0, 1, 2, 3, 4, 5, 6, 7 which can be written as

0 = 0*1 + 0*2 + 0*4
1 = 1*1 + 0*2 + 0*4
2 = 0*1 + 1*2 + 0*4
3 = 1*1 + 1*2 + 0*4
4 = 0 *1 + 0*2 + 1*4
5 = 1*1 + 0*2 + 1*4
6 = 0*1 + 1*2 + 1*4
7 = 1*1 + 1*2 + 1*4

 

[Werg22]

Another example, choosing a = 3 and n = 2.

0 = 0*1 + 0*3 + 0*9
1 = 1*1 + 0*3 + 0*9
2 = -1*1 + 1*3 + 0*9
3 = 0*1 + 1*3 + 0*9
4 = 1*1 + 1*3 + 0*9
5 = -1*1 + -1*3 + 1*9
6 = 0*1 + -1*3 + 1*9
7 = 1*1 + -1*3 + 1*9
8 = -1*1 + 0*3 + 1*9
9 = 0*1 + 0*3 + 1*9
10 = 1*1 + 0*3 + 1*9
11 = -1*1 + 1*3 + 1*3
12 = 0*1 + 1*3 + 1*9
13 = 1*1 + 1*3 + 1*9

 

[neutrino]

Isn't that converting binary to decimal? (This particular case at least)

 

[Werg22]

In the particular case of a = 2, yes.

 

[neutrino]

Oh, okay. I get it now. :)

 

[dodo]

The moment that a gets greater than 3, for example a=4, n=2 (using as powers the numbers 1, 4, 16), how can you get 2 as a sum, when you can't substract enough from 4 or 16, or add more to 1?

 

[Ben Niehoff]

Yep, it only works for a<4. After that, you need a larger set of coefficients b.

 

[Werg22]

The moment that a gets greater than 3, for example a=4, n=2 (using as powers the numbers 1, 4, 16), how can you get 2 as a sum, when you can't substract enough from 4 or 16, or add more to 1?

Okay, true. It seems to be only true with natural numbers lesser than 4 (with the restrictions on b). The question would be; can we associate successive strings of natural numbers to fixed sets of allowable coefficients for b? The string 1, 2, 3 is already bound to {-1, 0, 1}, I would think {-2, -1, 0, 1, 2} works for 4 but it doesn't work with 5, though {-3, -2, -1, 0, 1, 2, 3} seems to. The important thing here is that the set of allowable coefficients for b doesn't correspond to Z_a.

 

[dodo]

Well, they are beginning to get close to {0, 1, 2, 3, ... a-1}; somehow the negatives are compensating for the lack of a-1. Comparing to Z_a, several questions would apply:

• Is the expression unique? (that is, can each integer be obtained in just one way, or in redundant ways?)

• Can it really be done without repeating a power in the sum?

• What is the new maximum, given the new sets of b's? (compared to a^n - 1 for Z_a.)

 

[Werg22]

Well uniqueness here doesn't quite apply. We could choose strings of 2, (n, n+1) with the set of allowable coefficients being Z_n+1, it would obviously work since Z_n is contained in Z_n+1. Nor are constructs unique, there are a few examples with a = 3, b = 2 that can be written otherwise. But the the entire of object of interest here is whether or not it is possible to break the positive integers into strings, each associated with sets of allowable coefficients for b, with the property that in a string, if n is its greatest element, the set of allowable coefficients for b doesn't correspond to Z_n.