# Find the minimum positive-integer value which meets the requirement

If the equation is

Mod[515 Sum[10^(3 d), {d, 0, n}], 53] == 0


then I can get the minimum positive-integer value of n with

minint[x_, y_] :=
Module[{len = IntegerLength[x], n = 1},
While[! Divisible[x (Sum[10^(len d), {d, 0, n}]), y], n++]; n + 1]

minint[515, 53]


13

But if the equation is

Mod[305745211 Sum[10^(9 d), {d, 0, n}], 182593] == 0


the minint needs a long long time to run. I want to get a most high-efficiency method to do it. Help please.

PS:

The answer is $20288$ as I know.

• surely Mod[305745211 Sum[10^(6 d), {d, 0, n}], 182593] == 0 should be Mod[305745211 Sum[10^(9 d), {d, 0, n}], 182593] == 0 because 305745211 has 9 digits, not 6 – Manuel --Moe-- G Feb 23 '16 at 18:17
• Thanks for your point out,It is a typo.And I have corrected it. – yode Feb 23 '16 at 18:20
• Then the simple code in my answer is correct, and fast enough :) – Manuel --Moe-- G Feb 23 '16 at 18:23

No need to repeat all the summing in each step, just keep a running tally and add an appropriately updated increment.

m = 182593;
mult = Mod[10^6, m];
n1 = Mod[305745211, m];
next = n1;
val = n1;
j = 0;
AbsoluteTiming[
While[j <= 10^6 && Mod[val, m] != 0, j++; next = Mod[mult*next, m];
val += next]; j]

(* Out= {0.059061, 30431} *)

• +1 You could start just with val = next = 1; No need for n1 – Dr. belisarius Feb 23 '16 at 18:06
• @Dr.belisarius I haven't had enough coffee yet. – Daniel Lichtblau Feb 23 '16 at 18:38
• imgur.com/gallery/0ZDf13W – Dr. belisarius Feb 23 '16 at 19:00
• @Dr.belisarius If you have seen China's Spring Festival gala,more strange way to brewed it will turn up. – yode Feb 23 '16 at 19:23
• Is there a slip in current code? – yode Feb 23 '16 at 19:27

Borrowing the notation of @BobHanlon, the analytic solution to the sum is $x*Sum[10^{c*d},\{d,0,n\}]=x*(10^{c*(n+1)}-1)/(10^c-1)$.

Mod $m$, the equation may be written as follows

Mod[x,m] * (PowerMod[10, c*(n+1), m]-1) * PowerMod[PowerMod[10, c, m]-1, -1, m]


which takes advantage of the fast PowerMod mentioned by @DanielLichtblau.

Note that substituting values for $x$, $c$, and $m$ gives an equation like

z * (PowerMod[10,c*(n+1),m] - 1) = 0,


where $z$ is a positive integer. Hence, the problem simplifies to finding a solution for PowerMod[10,c*(n+1),m]=1.

MultiplicativeOrder[10,m] gives the smallest integer $k$ such that $10^k=1$, mod $m$. The smallest positive integer multiple of $k$, say $i*k$, giving an integer solution for $n$ in $i*k=c*(n+1)$ solves the problem with $n=i*k/c-1$.

For example, $x=515$, $c=3$, and $m=53$ requires PowerMod[10,3*(n+1),53]=1. In this case, MultiplicativeOrder[10,53]=13, and $n=i*13/3-1$. The smallest integer $n=12$ results for $i=3$.

The large example gives PowerMod[10,6*(n+1),182593]=1, and MultiplicativeOrder[10,182593]=182592. Thus, $n=i*182592/6-1=30431$ when $i=1$.

The only calculation required is MultiplicativeOrder[10,m], which takes zero time. MultiplicativeOrder is undefined when GCD[10,m]>1, but the two moduli given in the question were both prime.

Clear[f, minint]


Perform the Sum analytically.

f[x_, n_, c_] = x Sum[10^(c* d), {d, 0, n}];

minint[x_, y_, c_] := Module[{n = 1}, While[Mod[f[x, n, c], y] != 0, n++]; n]


Note that minint should return n vice n+1.

minint[515, 53, 3] // AbsoluteTiming

(*  {0.000105, 12}  *)


Verification that 12 is the correct value

Mod[515 Sum[10^(3 d), {d, 0, 12}], 53] == 0

(*  True  *)

minint[305745211, 182593, 6] // AbsoluteTiming

(*  {12.5941, 30431}  *)


Verification

Mod[305745211 Sum[10^(6 d), {d, 0, 30431}], 182593] == 0

(*  True  *)


I do not know if 13 seconds meets your efficiency requirement

• This would probably be quite fast with judicious use of PowerMod to avoid computing those large powers of 10 in f[x,n,c]. – Daniel Lichtblau Feb 23 '16 at 17:48

Pretty sure OP made a mistake in describing the problem. The problem is finding a zero mod of a large number made by repeating digits.

minint[x_, y_] := Block[
{lenX = IntegerLength[x], r = x, m = 1, n = 1},
While[! Divisible[r, y], m = 10^lenX*m; r = m*x + r; n++];
{n, r}
]


lets test with first correct example

minint[515,53]
(* {13, 515515515515515515515515515515515515515} *)


now lets test with second example that OP somewhat bungled the description

minint[305745211, 182593]
(* {20288,305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211305745211... *)


The integer is quite long indeed! (cut off for sanity)