Find the minimum positive-integer value which meets the requirement

Question

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.

Answer 1

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[1461]= {0.059061, 30431} *)

Answer 2

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.

Answer 3

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

Answer 4

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)