Finding Similar Sequences

89 Views Asked by At

Can we find two sequences:

$$\{a (b^0), a (b^1), a (b^2), a (b^3), \dots, a(b^n)\} \bmod p_1$$

$$\{c (d^0), c (d^1), c (d^2), c (d^3), \dots, c(d^n)\} \bmod p_2$$

that differ by only one number?

AN EXAMPLE

For example, I start with:

$$\{4^0, 4^1, 4^2, 4^3\} \equiv \{1, 4, 1, 4\} \bmod 5$$

I then take the sum of a similar sequence. For example, the same sequence modulo 10 is:

$$\{4^0, 4^1, 4^2, 4^3\} \equiv \{1, 4, 6, 4\} \bmod 10$$

Note that the sequences, for length 4, differ by only one number.

Is it possible to find two longer sequences that differs by only one number?

IF WE CAN GET A LONGER SEQUENCE, WHAT IS IT? HOW LONG CAN WE MAKE IT?

1

There are 1 best solutions below

4
On BEST ANSWER

As long as you wish,

In the end it is pretty easy: $$ \forall b, \forall x, \forall y, \forall z : \{b;x;y;z\}\subset \mathbb N\land \{y;z\}\not\subset \bigcup_{n=0}^\infty\{b^n\}\cup \{\forall n>b^{x-1}\}\\ \bigcup_{n=0}^x\{b^n\} \equiv \bigcup_{n=0}^{x-1}\{b^n\} \cup\{y\}\ \text {mod}\ { b^{x-1}-y}\equiv \bigcup_{n=0}^{x-1}\{b^n\} \cup\{z\}\ \text {mod}\ { b^{x-1}-z}\\ $$ Explaining a little better, all numbers should be naturals (obviously), $y$ and $z$ shouldn't be powers of $b$ (powers of $b$ are already included) nor shall they be greater than $b^x-(b-1)(b^{x-1})=b^{x-1}$ (otherwise, the the exponent in the modulus could be reduced - got this from the example below, only using $b=3$). The conclusion (and, in fact, many premises as well) is drawn from mathematical induction.

Here's an example (actually, this is one of the firsts I used to get to the generalization - from the above, the concretized variables are $b=2;\ x=5;\ y=3; z=2$): $$ \{2^0; 2^1; 2^2; 2^3; 2^4\} \equiv \{2^0; 2^1; 3; 2^2; 2^3\} \mod{ 2^4-3}\\ \{2^0; 2^1; 2^2; 2^3; 2^4\} \equiv \{2^0; 2^1; 2^2; 5; 2^3\} \mod{ 2^4-5 }\\ $$