9
$\begingroup$

I have problem solving this equation, smallest n such that $1355297$ divides $10^{6n+5}-54n-46$. I tried everything using my scientific calculator, but I never got the correct results(!).and finally I gave up!. Could you help me find the first 2 solutions for this equation ? (thanks.)

$\endgroup$
  • $\begingroup$ What did you try in MMA? $\endgroup$ – Ulrich Neumann Feb 9 '18 at 9:59
  • 2
    $\begingroup$ @Ulrich What is MMA ? $\endgroup$ – Bobby H Feb 9 '18 at 10:00
  • $\begingroup$ Sorry, Mathematica $\endgroup$ – Ulrich Neumann Feb 9 '18 at 10:12
  • 1
    $\begingroup$ O yes I am quite sure that $1355297$ divides $(10^{1836828602912}-9*1836828602911-10)$. I calculated this with my calculator. $\endgroup$ – Bobby H Feb 9 '18 at 10:33
  • $\begingroup$ Where does this question originate from? $\endgroup$ – Chip Hurst Feb 9 '18 at 16:14
8
$\begingroup$

$n_1 = 2331259$, $n_2 = 3776127$,

Obtained from this Mathematica code:

cf = Compile[{{m, _Integer}},
  Block[{n, a, b, p, counter = 0,result},
   result = ConstantArray[0, m];
   p = 1355297;
   n = 0;
   a = Mod[10^(5), p];
   b = 0;
   While[counter < m,
    n++;
    a = Mod[a 1000000, p];
    b = Mod[b - 54 , p];
    While[Mod[a + b - 46, 1355297] != 0,
     n++;
     a = Mod[a 1000000, p];
     b = Mod[b - 54 , p];
     ];
    counter++;
    result[[counter]] = n;
    ];
   result
   ],
  CompilationTarget -> "C"
  ];

cf[2]

{2331259, 3776127}

$\endgroup$
  • $\begingroup$ Thanks Henrik I really appreciate this ! : D $\endgroup$ – Bobby H Feb 9 '18 at 10:37
  • $\begingroup$ You're welcome! $\endgroup$ – Henrik Schumacher Feb 9 '18 at 10:39
11
$\begingroup$

There is no need for a brute force search. There is also no need for compilation, which may run into the maximum compiled integer limit. A faster solution follows from a bit of theory. You can get the first 225000 solutions (up to $n\approx 306$ billion) in less than a second.

The original equation is ${\rm Mod}[10^{6n+5}-54n-46,p]=0$, where $p=1355297$.

Let $m=6n+5$ and write the equation as PowerMod[10,m,p]=Mod[9m+1,p].

The period of the cycle of PowerMod[10,x,p] for $x=1,2,3,...$ equals the period of the decimal expansion of $1/p$, for prime $p$. The length of the repeating decimal of $1/p$ is MultiplicativeOrder[10,p] which, in this case, equals $p-1$.

MultiplicativeOrder[10, 1355297]

1355296

These are all 1355296 distinct residues in the repeating cycle. This pre-calculation takes about 3/4 second.

residues = PowerMod[10, Range[1355296], 1355297]

The two modular equations are:

$m=i+j*(p-1)$, mod $p$, with $1\le i \le p-1$, and $j\ge 1$, from length-$(p-1)$ cycle of residues for PowerMod[10,m,p]

$9m+1=k*p+r_i$, mod $p$, with $0\le k$, from Mod[9m+1,p]=ri, the i'th residue.

Multiply the first equation by 9 and equate to give $a*j+b*k=c$, where $a=9*(p-1)$, $b=-p$, and $c=r_i-1-9*i$. Solve this linear Diophantine equation via ExtendedGCD[a,b].

ExtendedGCD[9(p-1),-p]={g,{u,v}}

{1, {301177, 2710591}}

Only the first term, $u=301177$, of the second part is required.

There are infinitely many solutions $\{j,k\}=\{u*c+b*q,v*c-a*q\}$, where $q\ge $0 and $a*u+b*v=1$ is found via ExtendendGCD[a,b]. The smallest solution occurs when q=Quotient[u*c,p]. The last step is to sort those solutions $m$ equivalent to 5, mod 6.

The first roughly quarter million solutions are found in about 1/4 second. The fastest of the current 3 answers was from @MichaelE2, where the first 10 solutions are found in about 0.68 s.

Block[{p = 1355297, i, u, uc},
   u = ExtendedGCD[9 (p - 1), -p][[2, 1]];
   AbsoluteTiming[
      i = Range[Length[residues]];
      uc = u*(residues[[i]] - 1 - 9 i);
      (Sort[Pick[#, Mod[#, 6], 5] &[i + (p - 1) (uc - p*Quotient[uc, p])]] - 5)/6
  ]]

{0.230856, {2331259, 3776127, 5366598, 5505709, 5652052, 7317951,..., 306133783114, 306135079824, 306136273333}}

Subsequent solutions follow by decreasing the integer q=Quotient[uc,p].

$\endgroup$
  • 3
    $\begingroup$ Nice. Note that residues = NestList[Mod[10 #, 1355297] &, 10, Length@# - 1] &[Range[1355296]] is about 16 times faster than PowerMod, which makes the cost of pre-computing residues almost insignificant. (I figure PowerMod is advantageous when a single or sporadic values are needed.) $\endgroup$ – Michael E2 Feb 24 '18 at 19:36
  • $\begingroup$ @MichaelE2 Thanks for the tip here and before on slow PowerMod. I use it frequently, and will redefine it using your much faster NestList formulation. $\endgroup$ – KennyColnago Feb 25 '18 at 16:28
8
$\begingroup$

A more Mathematica way to do an exhaustive search:

pp = 1355297;
Pick[#,
 Mod[10^5 NestList[Mod[10^6 #, pp] &, 10^6, Length@# - 1] - (54 n + 46 /. n -> #), pp],
 0] &@ Range[10^7] // AbsoluteTiming

(*  {0.665031, {2331259, 3776127, 5366598, 5505709, 5652052, 7317951, 8306396, 8955772}} *)

The same applied to chunks, which quits after at least 2 solutions are found.

Last@NestWhile[
  Function[args,            (* args = {current range, current solutions *)
   With[{range = Range @@ args[[1]], sols = args[[2]]},
    With[{s = Flatten[{
         sols,
         Pick[range, 
          Mod[10^5 NestList[Mod[10^6 #, pp] &, 
              PowerMod[10^6, First@range, pp], 
              Length@range - 1] - (54 n + 46 /. n -> range),
           pp],
          0]
         }]},
     {args[[1]] + 10^6, s}  (* increment range *)
     ]]
   ],
  {{1, 10^6}, {}},          (* {initial range, initial solutions *)
  Length[#[[2]]] < 2 &,     (* min. number of solutions *)
  1,
  100                       (* MaxIterations *)
  ] // RepeatedTiming

(*  {0.27, {2331259, 3776127}}  *)

Somewhat surprisingly, it is faster than Henrik's compiled-to-C solution:

cf[2] // RepeatedTiming
(*  {0.283, {2331259, 3776127}}  *)

Remark: Disappointingly, PowerMod is slow, so I used NestList:

foo = NestList[Mod[10^6 #, pp] &, 10^6, Length@# - 1] &[Range[10^7]]; // AbsoluteTiming
(*  {0.480641, Null}  *)

murf = PowerMod[10^6, Range[10^7], pp]; // AbsoluteTiming
(*  {7.97349, Null}  *)

foo == murf
(*  True  *)
$\endgroup$
  • $\begingroup$ Very interesting! I tried to Complie your Mathematica Pick[]-approach, hoping to speed it up, but didn't succeed. What's wrong with find = Compile[{{mr, _Integer , 1}, {pz, _Integer }}, Block[{}, Pick[mr, Mod[10^5 NestList[Mod[10^6 mr, pz] &, 10^6, Length[mr] - 1] - (54 mr + 46), pz ](*Mod*), 0] ] ]? $\endgroup$ – Ulrich Neumann Feb 11 '18 at 15:37
  • 1
    $\begingroup$ @UlrichNeumann Unfortunately, Pick is not compilable. $\endgroup$ – Michael E2 Feb 11 '18 at 15:39
  • $\begingroup$ @ Michael E2: It's a pity,thanks. $\endgroup$ – Ulrich Neumann Feb 11 '18 at 15:48
7
$\begingroup$

How about this?

cf = Compile[{{max, _Integer}, {p, _Integer}, {j, _Integer}},
   Module[{list = ConstantArray[0, 0]},
    Do[
     If[
      PowerMod[10, 6 n + 5, p] - Mod[54 n + 46, p] == 0,
      AppendTo[list, n];
      If[Length[list] >= j, Break[]]
      ],
     {n, Range[1, max]}
     ];
    list
    ]
   ];

In[20]:= result = cf[10^8, 1355297, 2]

Out[20]= {2331259, 3776127}

Check the result:

In[21]:= Table[Mod[10^(6 n + 5) - 54 n - 46, 1355297], {n, result}]

Out[21]= {0, 0}
$\endgroup$
  • $\begingroup$ Hmpf. You beat me by 31 seconds... =) $\endgroup$ – Henrik Schumacher Feb 9 '18 at 10:32
  • $\begingroup$ =). I'm also going to say that my use of PowerMod is quite clever here. $\endgroup$ – Sjoerd Smit Feb 9 '18 at 10:35
  • $\begingroup$ Nah, it isn't... Check the timings. ;o) But I actually was looking for something like PowerMod but did not find it for some reason... $\endgroup$ – Henrik Schumacher Feb 9 '18 at 10:35
  • $\begingroup$ Why not the simple and obvious list = {} rather than the more obscure list = ConstantArray[0, 0]? $\endgroup$ – m_goldberg Feb 9 '18 at 13:13
  • 1
    $\begingroup$ I tried list = {}, but for some reason this coerces all elements added to the list to reals. ConstantArray[0, 0] was the easiest method I found to create an empty integer list. $\endgroup$ – Sjoerd Smit Feb 9 '18 at 14:02

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.