[FEATURE]: The Repunit theorem #208

New Issue

claunia · 2026-01-29T15:09:09Z

claunia commented

2026-01-29 15:09:09 +00:00

Originally created by @ridge-kimani on GitHub (Dec 11, 2025).

Detailed description

Add Repunit theorem

Issue details

Numbers formed by repeating digits or repeating blocks—such as 111111, 424424, or structures like 10ⁿ + 1 (e.g., 100000001)—follow predictable patterns in number theory. These patterns are not random; they arise from the multiplicative order of 10 modulo a prime.

Context

Right now, we treat these numbers as arbitrary integers, which leads to three core problems:

Missing mathematical behavior

Repeated-digit numbers have a very specific factorization rule (e.g., 100000001 being divisible by 17). Without modeling the underlying theorem, our current logic either:

gives no insight into why the divisibility works,
or forces us to compute divisibility using naive methods that scale poorly.

Inconsistent patterns in code

Because these numbers are treated on a case-by-case basis, any function that needs to handle:

repunits (111…1),
repeated digits (777777),
repeated blocks (XYZXYZ),
or cyclotomic structures (10ⁿ ± 1),

ends up re-implementing partial logic, often incorrectly or inefficiently. Bringing this into a unified mathematical rule improves maintainability and correctness.

Huge performance waste for large repeated patterns

Repeated-digit integers can be extremely large (sometimes more than a million digits long).

Using the multiplicative-order approach lets us compute divisibility using O(log n) modular arithmetic and without building the actual number at all.

With this algorithm in place, once the multiplicative order is part of the system, it unlocks:

fast repunit divisibility checks,
systematic analysis of repeated-digit numbers,
handling of cyclotomic expressions,
better support for prime testing involving decimal periodic.

I believe this will be a good one to tackle, given that it's an unresolved problem in number theory.

Examples

These examples show actual numbers, their patterns, and the mathematical reason they’re divisible by certain primes.

1. Classic example: 100000001 is divisible by 17

100000001 ÷ 17 = 5882353

Why?

100000001 = 10⁸ + 1
The multiplicative order of 10 modulo 17 is 8, meaning:

10⁸ ≡ 1 (mod 17)

So:

10⁸ + 1 ≡ 2 (mod 17)? No → but 10⁸ ≡ -1 (mod 17)

Actually:

10⁸ ≡ -1 (mod 17)

Therefore:

10⁸ + 1 ≡ 0 (mod 17)

2. Repeated block example: 424424

Block: 424
Repeated twice → total structure: 424424

Divisible by:

7, 11, 13 → because 1001 = 7 × 11 × 13

Why?

424424 = 424 × 1001, and:

1001 = 10³ + 1 = (10³ - 1)/9 × 9

The fact that 1001 factors into 7, 11, and 13 comes from the multiplicative order of 10 modulo those primes.

3. Repunit example: 111111

111111 is 6 repeated digits of 1.
It equals:

111111 = (10⁶ − 1) / 9

Divisible by:

Why these primes?

Because the multiplicative order of 10 modulo each of those primes divides 6.
For example:

ord₁₁(10) = 2 → and 2 divides 6
ord₃₇(10) = 3 → and 3 divides 6
ord₇(10) = 6 → and 6 divides 6

So all of them divide 111111.

4. Repeated digit example: 999999999 (9 repeated 9 times)

This is:

999,999,999 = 9 × 111,111,111

And 111,111,111 has divisors:

3
37
333667

Again, it is determined by which primes have multiplicative order dividing 9.

5. Three-block repeated pattern: XYZXYZXYZ

Example: 123123123

This is:

123 × 1,001,001

Prime factors of 1,001,001:

1,001,001 = 7 × 11 × 13 × 101 × 109

All these primes divide the repeated-block number because their orders divide 3×3.

6. Palindromic power example: 10⁶ − 1 = 999999

Divisible by:

9 → trivial because it's 9 repeated digits  
37  
3  
27

The factor 37 is the famous one here because:

999 = 27 × 37

which again is tied to the order of 10 modulo 37 (which is 3).

7. Full reptend prime example

A prime is "full reptend" in base 10 if the order of 10 mod p is p−1.

Example:

7 is a full reptend prime.
10 has order 6 mod 7.

This is why:

1/7 = 0.142857142857… (repeats every 6 digits)

and why repunit length = 6.

Possible workarounds

No response

Additional information

No response

Additional Information

No response

Possible implementation

No response

Additional information

No response

Originally created by @ridge-kimani on GitHub (Dec 11, 2025). ### Detailed description Add Repunit theorem ### Issue details Numbers formed by repeating digits or repeating blocks—such as 111111, 424424, or structures like 10ⁿ + 1 (e.g., 100000001)—follow predictable patterns in number theory. These patterns are not random; they arise from the multiplicative order of 10 modulo a prime. ### Context Right now, we treat these numbers as arbitrary integers, which leads to three core problems: 1. Missing mathematical behavior Repeated-digit numbers have a very specific factorization rule (e.g., 100000001 being divisible by 17). Without modeling the underlying theorem, our current logic either: - gives no insight into why the divisibility works, - or forces us to compute divisibility using naive methods that scale poorly. 2. Inconsistent patterns in code Because these numbers are treated on a case-by-case basis, any function that needs to handle: - repunits (111…1), - repeated digits (777777), - repeated blocks (XYZXYZ), - or cyclotomic structures (10ⁿ ± 1), ends up re-implementing partial logic, often incorrectly or inefficiently. Bringing this into a unified mathematical rule improves maintainability and correctness. 3. Huge performance waste for large repeated patterns Repeated-digit integers can be extremely large (sometimes more than a million digits long). Using the multiplicative-order approach lets us compute divisibility using O(log n) modular arithmetic and without building the actual number at all. With this algorithm in place, once the multiplicative order is part of the system, it unlocks: - fast repunit divisibility checks, - systematic analysis of repeated-digit numbers, - handling of cyclotomic expressions, - better support for prime testing involving decimal periodic. I believe this will be a good one to tackle, given that it's an unresolved problem in number theory. ### Examples These examples show actual numbers, their patterns, and the mathematical reason they’re divisible by certain primes. #### **1. Classic example: 100000001 is divisible by 17** ``` 100000001 ÷ 17 = 5882353 ``` Why? `100000001 = 10⁸ + 1` The multiplicative order of 10 modulo 17 is **8**, meaning: ``` 10⁸ ≡ 1 (mod 17) ``` So: ``` 10⁸ + 1 ≡ 2 (mod 17)? No → but 10⁸ ≡ -1 (mod 17) ``` Actually: ``` 10⁸ ≡ -1 (mod 17) ``` Therefore: ``` 10⁸ + 1 ≡ 0 (mod 17) ``` --- #### **2. Repeated block example: 424424** Block: `424` Repeated twice → total structure: `424424` Divisible by: ``` 7, 11, 13 → because 1001 = 7 × 11 × 13 ``` Why? `424424 = 424 × 1001`, and: ``` 1001 = 10³ + 1 = (10³ - 1)/9 × 9 ``` The fact that 1001 factors into 7, 11, and 13 comes from the multiplicative order of 10 modulo those primes. --- #### **3. Repunit example: 111111** `111111` is `6` repeated digits of `1`. It equals: ``` 111111 = (10⁶ − 1) / 9 ``` Divisible by: ``` 3 7 11 13 37 ``` Why these primes? Because the multiplicative order of 10 modulo each of those primes divides 6. For example: * ord₁₁(10) = 2 → and 2 divides 6 * ord₃₇(10) = 3 → and 3 divides 6 * ord₇(10) = 6 → and 6 divides 6 So all of them divide `111111`. --- #### **4. Repeated digit example: 999999999 (9 repeated 9 times)** This is: ``` 999,999,999 = 9 × 111,111,111 ``` And `111,111,111` has divisors: ``` 3 37 333667 ``` Again, it is determined by which primes have multiplicative order dividing 9. --- #### **5. Three-block repeated pattern: XYZXYZXYZ** Example: `123123123` This is: ``` 123 × 1,001,001 ``` Prime factors of 1,001,001: ``` 1,001,001 = 7 × 11 × 13 × 101 × 109 ``` All these primes divide the repeated-block number because their orders divide 3×3. --- #### **6. Palindromic power example: 10⁶ − 1 = 999999** Divisible by: ``` 9 → trivial because it's 9 repeated digits 37 3 27 ``` The factor `37` is the famous one here because: ``` 999 = 27 × 37 ``` which again is tied to the order of 10 modulo 37 (which is 3). --- #### **7. Full reptend prime example** A prime is "full reptend" in base 10 if the order of 10 mod p is p−1. Example: ``` 7 is a full reptend prime. 10 has order 6 mod 7. ``` This is why: ``` 1/7 = 0.142857142857… (repeats every 6 digits) ``` and why repunit length = 6. ### Possible workarounds _No response_ ### Additional information _No response_ ### Additional Information _No response_ ### Possible implementation _No response_ ### Additional information _No response_

claunia added the Stale enhancement labels 2026-01-29 15:09:09 +00:00

claunia closed this issue

2026-01-29 15:09:11 +00:00

claunia commented

2026-01-29 15:09:12 +00:00

@github-actions[bot] commented on GitHub (Jan 11, 2026):

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@github-actions[bot] commented on GitHub (Jan 11, 2026): This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

claunia commented

2026-01-29 15:09:14 +00:00

@github-actions[bot] commented on GitHub (Jan 19, 2026):

Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our Gitter channel or our Discord server. Thank you for your contributions!

@github-actions[bot] commented on GitHub (Jan 19, 2026): Please ping one of the maintainers once you add more information and updates here. If this is not the case and you need some help, feel free to ask for help in our [Gitter](https://gitter.im/TheAlgorithms) channel or our [Discord server](https://the-algorithms.com/discord/). Thank you for your contributions!

claunia referenced this issue

2026-01-29 15:13:11 +00:00

[PR #209] [CLOSED] added queue,stack operations and pattern matching algorithm #485

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/C#208