Problems & Puzzles: Puzzles

Puzzle 565.- [(d)n] mod d^n = k

JM Bergot sent the following puzzle:

[(d)n] mod d^n = k for a consecutive set of values of n....(A)

Example:

If d=2, (A) is true for n=4, 5, 6 & 7

2222 mod 2^4 =14
22222 mod 2^5 =14
222222 mod 2^6 =14
2222222 mod 2^7 =14

Q. Can you find another interesting/larger case?

Contributed Torbjörn Alm, Farid Lian & Anton Vrba.

***

Torbjörn Alm wrote:

I run the possible d values from 2 to 9 and n up to 50.

For n = 2 I found groups of 4 nvalues every 6 n, i.e. for n=4, 10, 16 ...46
and for n=5 I found groups of 2 n-values for every 6 n, i.e. n= 6, 12, 18,...49.

For the remaining n-values there not a single case.

10  +2222222222 mod 2^10 = +910
11  +22222222222 mod 2^11 = +910
12  +222222222222 mod 2^12 = +910
13  +2222222222222 mod 2^13 = +910

16  +2222222222222222 mod 2^16 = +58254
17  +22222222222222222 mod 2^17 = +58254
18  +222222222222222222 mod 2^18 = +58254
19  +2222222222222222222 mod 2^19 = +58254

22  +2222222222222222222222 mod 2^22 = +3728270
23  +22222222222222222222222 mod 2^23 = +3728270
24  +222222222222222222222222 mod 2^24 = +3728270
25  +2222222222222222222222222 mod 2^25 = +3728270

...

46  +2222222222222222222222222222222222222222222222 mod 2^46 = +62549994824590
47  +22222222222222222222222222222222222222222222222 mod 2^47 = +62549994824590
48  +222222222222222222222222222222222222222222222222 mod 2^48 = +62549994824590
49  +2222222222222222222222222222222222222222222222222 mod 2^49 = +62549994824590

6  +555555 mod 5^6 = +8680
7  +5555555 mod 5^7 = +8680

12  +555555555555 mod 5^12 = +135633680
13  +5555555555555 mod 5^13 = +135633680

18  +555555555555555555 mod 5^18 = +2119276258680
19  +5555555555555555555 mod 5^19 = +2119276258680
...

48  +555555555555555555555555555555555555555555555555 mod 5^48 = +1973729821555833849642011854383680
49  +5555555555555555555555555555555555555555555555555 mod 5^49 = +1973729821555833849642011854383680

The fact that only 2 and 5 behave like this depends of caouse of the fact that the number base is 10.
 

***

Farid wrote:

In developing this problem, I found that when more than one

 

 

value of n consecutive k repeated sequence also occurs

 

 

regular in this set is repeated for consecutive equal values of k continuously 

 

(until infinity?) that the limit of reason

 

 

 

k values equal to the set of n consecutive, equal in the following

 

 

set of consecutive values of n, is expressed as follows:

 

 

 

 

 

 

 

 

 

 

Lim (ki/ki-1) = d^Δn, where:

 

 

 

 

k ---> ∞

 

 

 

 

 

 

∆n = delta between two n init of each set at same time consecutive.

 

 

 

 

 

 

 

 

Example:

 

 

 

 

 

 

For d = 2:

 

 

 

 

 

 

[(2)1] mod 2^1 = 0

 

 

 

 

 

[(2)2] mod 2^2 = 2

 

 

 

 

 

[(2)3] mod 2^3 = 6

 

 

 

 

 

[(2)4] mod 2^4 = 14 <---- first set of n consecutives.

 

 

 

[(2)5] mod 2^5 = 14

 

 

 

 

 

[(2)6] mod 2^6 = 14

 

 

 

 

 

[(2)7] mod 2^7 = 14

 

 

 

 

 

[(2)8] mod 2^8 = 142

 

 

 

 

 

[(2)9] mod 2^9 = 398

 

 

 

 

 

[(2)10] mod 2^10 = 910 <---- second set of n consecutives

 

 

[(2)11] mod 2^11 = 910

 

 

 

 

 

[(2)12] mod 2^12 = 910

 

 

 

 

 

[(2)13] mod 2^13 = 910

 

 

 

 

 

[(2)14] mod 2^14 = 9102

 

 

 

 

 

[(2)15] mod 2^15 = 25486

 

 

 

 

[(2)16] mod 2^16 = 58254 <---- third set of n  consecutives.

 

 

[(2)17] mod 2^17 = 58254

 

 

 

 

[(2)18] mod 2^18 = 58254

 

 

 

 

[(2)19] mod 2^19 = 58254

 

 

 

 

[(2)20] mod 2^20 = 582542

 

 

 

 

[(2)21] mod 2^21 = 1631118

 

 

 

 

[(2)22] mod 2^22 = 3728270 <---- fourth set of n consecutives … and so on…

 

[(2)23] mod 2^23 = 3728270

 

 

 

 

[(2)24] mod 2^24 = 3728270

 

 

 

 

[(2)25] mod 2^25 = 3728270

 

 

 

 

 

 

 

 

 

 

 

Here: ∆n = 10 - 4 = 16 - 10 = 22 - 16 = 6.

 

 

 

 

 

 

 

 

 

 

k = 14, 910, 58254, 3728270…

 

 

 

 

 

 

 

 

 

 

 

910/14 =

 

 

 

 

 

 

65

 

 

 

 

 

 

 

 

 

 

 

 

 

58254/910 =

 

 

 

 

 

 

64,0153846

 

 

 

 

 

 

 

 

 

 

 

 

 

37128270/58254 =

 

 

 

 

 

64,0002403

 

 

 

 

 

 

 

 

 

 

 

 

 

:

 

 

 

 

 

 

ki / ki-1 = 64 = d∆n = 26.

 

 

 

 

 

This is true for all cases that I founded for d values evaluated:

 

 

If  i is the size of n consecutives for k repeated, the table of values of d, i and ∆n will:

d

i

∆n

Lim (k/k-1) = d∆n

 

 

 

2

4

6

64

 

 

 

5

2

6

15625

 

 

 

10

2

2

100

 

 

 

20

2

30

20^30

 

 

 

25

2

15

25^15

 

 

 

50

2

30

50^30

 

 

 

100

2

3 & 6

100^3 & 100^6

 

 

 

125

2

12

125^12

 

 

 

143

2

1

143

only one occurrence

 

200

2

11 & 14

200^11 & 200^14

 

 

 

250

2

18

250^18

 

 

 

500

2

36

500^36

 

 

 

1000

tested

 

 

 

 

 

1250

tested

 

 

 

 

 

2000

tested

 

 

 

 

 

2500

tested

 

 

 

 

 

5000

tested

 

 

 

 

 

10000

tested

 

 

 

 

 

12500

tested

 

 

 

 

 

20000

tested

 

 

 

 

 

25000

tested

 

 

 

 

 

50000

tested

 

 

 

 

 

100000

conjetura

 

 

 

 

 

125000

conjetura

 

 

 

 

 

200000

conjetura

 

 

 

 

 

250000

conjetura

 

 

 

 

 

500000

conjetura

 

 

 

 

 

1000000

conjetura

 

 

 

 

 

1250000

conjetura

 

 

 

***

Anton Vrba wrote:

We note that there are repeated solutions of [(2)n] mod 2^n = k for consecutive n, at n = 6 m+4  which  indicates a pattern. We also note that 2222 = 2*1111 that is a digit times a repunit  and searching for this pattern using generalized or   base-b repunits soon reveals following:

A base-b repunit is defined as  R[b,n] = (b^n-1)/(b-1) and for the case  b = 2^q+2 we find above mentioned  pattern again and we can conjecture (as there is no proof) and write:

 2 R[2^q+2, q+p] mod  2^(q+p)  = 2^(q+1)-2   for   p= 1, 2 …. q+1

and these sequences repeat at n = 2 q(m+1) + 1

Bergot’s example is for q=3 and we can find Bergot’s sequences to any length just by changing the number base.

Example:  q=10,  b=2^10+2 = 1026

[(2)n] (base 1026)  mod 2^n = 2^11-2   for   n=11,12,…22 

One can generalize further and change the repeated digit d, unfortunately there is no nice solution as for the above case d=2 but one can conjecture: 

For the case  b = d^q+d    there exist an r  such that there is a solution 

d R[d^q+d, ,r+p] mod  d^(r+p)] = k   for   p= 1, 1,2 …. q+1

Example:  d=3;   q=8;   b=3^8+3 = 6564;  r=185

k=55516363584578627563714802636925932160577108325280017016577943761936902977368488012124482

Or [(3)n](base 6564) mod 3^n= y for 9 consecutive n=185, 186, … 194

***

 

 
Records   |  Conjectures  |  Problems  |  Puzzles