1
$\begingroup$

While others have already mentioned the divisibility of decimal repunits,

$$m := \frac{{10}^n - 1}{9}.$$

 1  1
 2  11                                11
 3  111                               3 37
 4  1111                              11 101

 5  11111                             41 271
 6  111111                            3 7 11 13 37
 7  1111111                           239 4649
 8  11111111                          11 73 101 137

 9  111111111                         3^2 37 333667
10  1111111111                        11 41 271 9091
11  11111111111                       21649 513239
12  111111111111                      3 7 11 13 37 101 9901

13  1111111111111                     53 79 265371653
14  11111111111111                    11 239 4649 909091
15  111111111111111                   3 31 37 41 271 2906161
16  1111111111111111                  11 17 73 101 137 5882353

17  11111111111111111                 2071723 5363222357
18  111111111111111111                3^2 7 11 13 19 37 52579 333667
19  1111111111111111111               1111111111111111111
20  11111111111111111111              11 41 101 271 3541 9091 27961

21  111111111111111111111             3 37 43 239 1933 4649 10838689
22  1111111111111111111111            11^2 23 4093 8779 21649 513239
23  11111111111111111111111           11111111111111111111111
24  111111111111111111111111          3 7 11 13 37 73 101 137 9901 99990001

25  1111111111111111111111111         41 271 21401 25601 182521213001
26  11111111111111111111111111        11 53 79 859 265371653 1058313049
27  111111111111111111111111111       3^3 37 757 333667 440334654777631
28  1111111111111111111111111111      11 29 101 239 281 4649 909091 121499449

29  11111111111111111111111111111     3191 16763 43037 62003 77843839397
30  111111111111111111111111111111    3 7 11 13 31 37 41 211 241 271 2161 9091 2906161
31  1111111111111111111111111111111   2791 6943319 57336415063790604359

I think a practical use of this divisibility is frequently overlooked :

  • For really gigantic inputs, one may literally stack wide band of digits on top of each others, and sum up the stacks, before performing any sort of modular arithmetic.

e.g. 12 111111111111 : 3 7 11 13 37 101 9901

One can stack every 12-digits directly on top of each other if one wants to calculate any of the combination of all these prime factors, which would massively speed up primality checking for small factors

for instance, to perform a quick test on

  7407457283755447477426709403332725993034294823928945951559129
  6149310316146786637645823164508144688817069018866259431952169

                             74 
 + 074572837554 =   74572837628 
 + 474774267094 =  549347104722 
 + 033327259930 =  582674364652 

 + 342948239289 =  925622603941 
 + 459515591296 = 1385138195237 
 + 149310316146 = 1534448511383 

 + 786637645823 = 2321086157206 
 + 164508144688 = 2485594301894 
 + 817069018866 = 3302663320760 
 + 259431952169 = 3562095272929
 ------------------------------
              3,562,095,272,929

Let's test them all except 9901 :

3 * 7 * 11 * 13 * 37 * 101 := 11,222,211

 ( 3562095272929 % 11222211 ) %   3 := ( 8390575 %   3 ) :=    1 | 3562095272929 %   3 ==   1 
 ( 3562095272929 % 11222211 ) %   7 := ( 8390575 %   7 ) :=    4 | 3562095272929 %   7 ==   4 
 ( 3562095272929 % 11222211 ) %  11 := ( 8390575 %  11 ) :=    6 | 3562095272929 %  11 ==   6 
 ( 3562095272929 % 11222211 ) %  13 := ( 8390575 %  13 ) :=   11 | 3562095272929 %  13 ==  11 
 ( 3562095272929 % 11222211 ) %  37 := ( 8390575 %  37 ) :=   11 | 3562095272929 %  37 ==  11 
 ( 3562095272929 % 11222211 ) % 101 := ( 8390575 % 101 ) :=    0 | 3562095272929 % 101 ==   0

Which indeed, has correctly identified 101 as a factor, since the original value was generated via

    7407457283755447477426709403332725993034294823928945951559129
    6149310316146786637645823164508144688817069018866259431952169: 101^13 23456789^13

So instead of requiring a big-integer library, even before we perform any sort of modular arithmetic on it, this chunking approach already pre-reduced the problem to something that can fit within 64-bit data types.

$\endgroup$
11
  • 2
    $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Feb 13 at 22:08
  • $\begingroup$ So like: math.stackexchange.com/a/3152669/903195 but also not phrased as a question. $\endgroup$
    – Roddy MacPhee
    Commented Feb 13 at 22:28
  • $\begingroup$ Also chunking is still modulo just using size carmichael totient ... $\endgroup$
    – Roddy MacPhee
    Commented Feb 13 at 22:49
  • $\begingroup$ @RoddyMacPhee : It's just an extrapolation of an existing idea so one wouldn't have to re-perform the same chunking for other primes that share common properties when performing upfront pre-filtering of small primes during primality check. Another point I didn't mention above is using a rapid mod 11 test for palindromes, which would be a huge time saver when the left and right halves don't even match. $\endgroup$
    – RARE Kpop Manifesto
    Commented Feb 15 at 2:33
  • $\begingroup$ @RoddyMacPhee : or for something like mod 3, even chunking decimal digits, no matter how wide, is waaaay too slow. $\endgroup$
    – RARE Kpop Manifesto
    Commented Feb 15 at 2:38

0

Reset to default