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