The Background
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 222
or 4444444444444444
, but repunits consist only of 1
.
The first couple repunits are therefore 1
, 11
, 111
, etc. These are referred to by Rn, so R1=1
, R2=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
...
The Challenge
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
where 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 x
before).
The Examples
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)
The Extras:
- Your code can do anything or nothing if
n < 2
. - You can assume a "reasonable" upper limit for
n
for testing and execution purposes -- your code will not be expected to output forn = 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.