Folks were talking prime factorization in chat and we found ourselves talking about repunits. Repunits are a subset of the numbers known as repdigits, which are numbers consisting of only repeating digits, like
4444444444444444, but repunits consist only of
The first couple repunits are therefore
111, etc. These are referred to by Rn, so R1=
11, etc., and are generated by the formula
R(n) = (10^n - 1)/9, with
n > 0.
Prime factorization of these repunit numbers follows sequence A102380 in the OEIS. For example:
R1 = 1
R2 = 11
R3 = 111 = 3 * 37
R4 = 1111 = 11 * 101
R5 = 11111 = 41 * 271
R6 = 111111 = 3 * 7 * 11 * 13 * 37
R7 = 1111111 = 239 * 4649
Write a program or function which, when given an input integer n with
n >= 2 via STDIN or equivalent, outputs or returns the novel prime factors for Rn, in any convenient format. "Novel prime factors" here means all
x is a prime factor of Rn, but
x is not a prime factor for any previous Rk, with
1 <= k < n (i.e., if we write the prime factors for all R in sequence, we've not seen
Input: 6 Output: 7, 13 (because 3, 11, and 37 are factors of a smaller R_k) Input: 19 Output: 1111111111111111111 (because R_19 is prime, so no other factors) Input: 24 Output: 99990001 (because 3, 7, 11, 13, 37, 73, 101, 137, 9901 are factors of a smaller R_k) Input: 29 Output: 3191, 16763, 43037, 62003, 77843839397 (because no factors of R_29 are also factors of a smaller R_k)
- Your code can do anything or nothing if
n < 2.
- You can assume a "reasonable" upper limit for
nfor testing and execution purposes -- your code will not be expected to output for
n = 10000000, for example, but your algorithm should work for such a case if given unlimited computing power and time.
- Here is a site dedicated to the factorizations of repunits for reference.
- I've not gone through the math, but I propose a hypothesis that every n has a distinct result for this algorithm -- that is, no n exists such that Rn has no novel factors.
I'll offer a 250-point bounty if someone proves or disproves that in their answer.Thomas Kwa proposed an elegant proof, and I awarded the bounty.