3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Manuel --Moe-- G Feb 23 '16 at 18:17
  • $\begingroup$ Thanks for your point out,It is a typo.And I have corrected it. $\endgroup$ – yode Feb 23 '16 at 18:20
  • $\begingroup$ Then the simple code in my answer is correct, and fast enough :) $\endgroup$ – Manuel --Moe-- G Feb 23 '16 at 18:23
  • $\begingroup$ @Manuel--Moe--G I'm studying what you have write.And thanks for your concern about this :). $\endgroup$ – yode Feb 23 '16 at 18:49
3
$\begingroup$

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

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.

$\endgroup$
1
$\begingroup$
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

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

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.