Skip to content

Instantly share code, notes, and snippets.

@mlliarm

mlliarm/factoring.md

Last active February 25, 2022 06:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mlliarm/f181b25684f4797f8815010a3f99dfd6 to your computer and use it in GitHub Desktop.
Save mlliarm/f181b25684f4797f8815010a3f99dfd6 to your computer and use it in GitHub Desktop.
Download ZIP
Factoring 10...01
Raw
factoring.md

Factoring 10...01

Tools

GNU/Linux factor Bash tool and python3.

Code & results

# bash shell
 $ factor 101
101: 101
 $ factor 1001
1001: 7 11 13
 $ factor 10001
10001: 73 137
 $ factor 100001
100001: 11 9091
 $ factor 1000001
1000001: 101 9901
 $ factor 10000001
10000001: 11 909091
 $ factor 100000001
100000001: 17 5882353
 $ factor 1000000001
1000000001: 7 11 13 19 52579
 $ factor 10000000001
10000000001: 101 3541 27961
 $ factor 100000000001
100000000001: 11 11 23 4093 8779
 $ factor 1000000000001
1000000000001: 73 137 99990001
 $ factor 10000000000001
10000000000001: 11 859 1058313049
 $ factor 100000000000001
100000000000001: 29 101 281 121499449
 $ factor 1000000000000001
1000000000000001: 7 11 13 211 241 2161 9091
 $ factor 10000000000000001
10000000000000001: 353 449 641 1409 69857
 $ factor 100000000000000001
100000000000000001: 11 103 4013 21993833369
 $ factor 1000000000000000001
1000000000000000001: 101 9901 999999000001
 $ factor 10000000000000000001
10000000000000000001: 11 909090909090909091
 $ factor 100000000000000000001
100000000000000000001: 73 137 1676321 5964848081
 $ factor 1000000000000000000001
1000000000000000000001: 7 7 11 13 127 2689 459691 909091
 $ factor 10000000000000000000001
10000000000000000000001: 89 101 1052788969 1056689261
 $ factor 100000000000000000000001
100000000000000000000001: 11 47 139 2531 549797184491917
 $ factor 1000000000000000000000001
1000000000000000000000001: 17 5882353 9999999900000001
 $ factor 10000000000000000000000001
10000000000000000000000001: 11 251 5051 9091 78875943472201
 $ factor 100000000000000000000000001
100000000000000000000000001: 101 521 1900381976777332243781
 $ factor 1000000000000000000000000001
1000000000000000000000000001: 7 11 13 19 52579 70541929 14175966169
 $ factor 10000000000000000000000000001
10000000000000000000000000001: 73 137 7841 127522001020150503761
 $ factor 100000000000000000000000000001
100000000000000000000000000001: 11 59 154083204930662557781201849
 $ factor 1000000000000000000000000000001
1000000000000000000000000000001: 61 101 3541 9901 27961 4188901 39526741
 $ factor 10000000000000000000000000000001
10000000000000000000000000000001: 11 909090909090909090909090909091
 $ factor 100000000000000000000000000000001
100000000000000000000000000000001: 19841 976193 6187457 834427406578561
 $ factor 1000000000000000000000000000000001
1000000000000000000000000000000001: 7 11 11 13 23 4093 8779 599144041 183411838171
 $ factor 10000000000000000000000000000000001
10000000000000000000000000000000001: 101 28559389 1491383821 2324557465671829
 $ factor 100000000000000000000000000000000001
100000000000000000000000000000000001: 11 9091 909091 4147571 265212793249617641
 $ factor 1000000000000000000000000000000000001 
1000000000000000000000000000000000001: 73 137 3169 98641 99990001 3199044596370769
 $ factor 10000000000000000000000000000000000001
10000000000000000000000000000000000001: 11 7253 422650073734453 296557347313446299
 $ factor 100000000000000000000000000000000000001
100000000000000000000000000000000000001: 101 722817036322379041 1369778187490592461
 $ factor 1000000000000000000000000000000000000001
factor: ‘1000000000000000000000000000000000000001’ is too large

Interesting observations

  • From 101 to 100000000000000000000000000000000000001 there's been only one prime: 101.

  • Most of the 10...01 numbers have more than one divisors. Those that have the least divisors (two) are:

    • 10001: 73 137
    • 100001: 11 9091
    • 1000001: 101 9901
    • 10000001: 11 909091
    • 100000001: 17 5882353
    • 10000000000000000001: 11 909090909090909091
    • 10000000000000000000000000000001: 11, 909090909090909090909090909091.

  • We notice that the following numbers have divisors with very similar structure:

    • 100001: 11 9091
    • 10000001: 11 909091
    • 10000000000000000001: 11 909090909090909091
    • 10000000000000000000000000000001: 11, 909090909090909090909090909091.

  • From the previous observation a questions is raised about the numbers that have divisors 11 and numbers with the structure 90..9091. Is there some underlying pattern? Did an experiment that was illuminating:

    # python3.x
s = "91"
t = "90"
for i in range(35):
  r = i*t + s
  res = 11*int(r)
  print("11*{}: ".format(r), res, "  len(res): {}".format(len(str(res))))
# RESULTS:
# --------
11*91:  1001   len(res): 4
11*9091:  100001   len(res): 6
11*909091:  10000001   len(res): 8
11*90909091:  1000000001   len(res): 10
11*9090909091:  100000000001   len(res): 12
11*909090909091:  10000000000001   len(res): 14
11*90909090909091:  1000000000000001   len(res): 16
11*9090909090909091:  100000000000000001   len(res): 18
11*909090909090909091:  10000000000000000001   len(res): 20
11*90909090909090909091:  1000000000000000000001   len(res): 22
11*9090909090909090909091:  100000000000000000000001   len(res): 24
11*909090909090909090909091:  10000000000000000000000001   len(res): 26
11*90909090909090909090909091:  1000000000000000000000000001   len(res): 28
11*9090909090909090909090909091:  100000000000000000000000000001   len(res): 30
11*909090909090909090909090909091:  10000000000000000000000000000001   len(res): 32
11*90909090909090909090909090909091:  1000000000000000000000000000000001   len(res): 34
11*9090909090909090909090909090909091:  100000000000000000000000000000000001   len(res): 36
11*909090909090909090909090909090909091:  10000000000000000000000000000000000001   len(res): 38
11*90909090909090909090909090909090909091:  1000000000000000000000000000000000000001   len(res): 40
11*9090909090909090909090909090909090909091:  100000000000000000000000000000000000000001   len(res): 42
11*909090909090909090909090909090909090909091:  10000000000000000000000000000000000000000001   len(res): 44
11*90909090909090909090909090909090909090909091:  1000000000000000000000000000000000000000000001   len(res): 46
11*9090909090909090909090909090909090909090909091:  100000000000000000000000000000000000000000000001   len(res): 48
11*909090909090909090909090909090909090909090909091:  10000000000000000000000000000000000000000000000001   len(res): 50
11*90909090909090909090909090909090909090909090909091:  1000000000000000000000000000000000000000000000000001   len(res): 52
11*9090909090909090909090909090909090909090909090909091:  100000000000000000000000000000000000000000000000000001   len(res): 54
11*909090909090909090909090909090909090909090909090909091:  10000000000000000000000000000000000000000000000000000001   len(res): 56
11*90909090909090909090909090909090909090909090909090909091:  1000000000000000000000000000000000000000000000000000000001   len(res): 58
11*9090909090909090909090909090909090909090909090909090909091:  100000000000000000000000000000000000000000000000000000000001   len(res): 60
11*909090909090909090909090909090909090909090909090909090909091:  10000000000000000000000000000000000000000000000000000000000001   len(res): 62
11*90909090909090909090909090909090909090909090909090909090909091:  1000000000000000000000000000000000000000000000000000000000000001   len(res): 64
11*9090909090909090909090909090909090909090909090909090909090909091:  100000000000000000000000000000000000000000000000000000000000000001   len(res): 66
11*909090909090909090909090909090909090909090909090909090909090909091:  10000000000000000000000000000000000000000000000000000000000000000001   len(res): 68
11*90909090909090909090909090909090909090909090909090909090909090909091:  1000000000000000000000000000000000000000000000000000000000000000000001   len(res): 70
11*9090909090909090909090909090909090909090909090909090909090909090909091:  100000000000000000000000000000000000000000000000000000000000000000000001   len(res): 72

Conclusion

From our experiments we can conjecture the following:

Conjecture

  • Every number of the type 10...01 with even number of zeroes more than four (6, 8, 10, ...) can be created by multiplying 11 with numbers of the type 90...9091.
  • The number 1001 is being created by multiplying 11 with 91. From there on, the rest of such numbers are created by multiplying 11 with 9091 (100001), 909091 (10000001), 90909091 (1000000001), etc.

First five examples:

  • 1001: 11 * 91 (base case), no of zeroes is 2
  • 100001: 11 * 9091 (first case), no of zeroes is 4
  • 10000001: 11 * 909091 (second case), no of zeroes is 6
  • 1000000001: 11 * 90909091 (third case), no of zeroes is 8
  • 100000000001: 11 * 9090909091 (fourth case), no of zeroes is 10

Final thoughts

THE PURPOSE OF COMPUTING

IS INSIGHT, NOT NUMBERS

R. W. Hamming

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment