Novel Prime Factors of Repunits

Question

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 R_n, so R₁=1, R₂=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:

R₁ = 1
R₂ = 11
R₃ = 111 = 3 * 37
R₄ = 1111 = 11 * 101
R₅ = 11111 = 41 * 271
R₆ = 111111 = 3 * 7 * 11 * 13 * 37
R₇ = 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 R_n, in any convenient format. "Novel prime factors" here means all x where x is a prime factor of R_n, but x is not a prime factor for any previous R_k, 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 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 R_n 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.

Answer 1

Pyth, 16 14 13 bytes

-F_m{P/^Td9SQ

As best I can tell, 19 takes forever.

-F_m{P/^Td9SQ      Implicit: Q = input
           SQ      Inclusive range 1 to Q
                        Implicit lambda d:
    {P                  unique primes dividing
       ^Td              10**d
      /   9                  //9
   m               map lambda over the range
   m{P/^Td9SQ      Unique prime factors of all repunits up to the Qth
  _                Reverse the list
-F                 Reduce by set difference

Try it here.

Answer 2

Proof that every repunit has a novel prime factor

Using Zsigmondy's Theorem, the proof is simple. From Wikipedia:

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a > b > 0 are coprime integers, then for any integer n ≥ 1, there is a prime number p (called a primitive prime divisor) that divides aⁿ − bⁿ and does not divide a^k − b^k for any positive integer k < n, with the following exceptions: [things that don't apply here].

Consider the repunits times 9: that is, 10ⁿ-1. By Zsigmondy's Theorem with a=10, b=1, there is some prime p | 10ⁿ-1 that does not divide any 10^k-1, k < n.

• Since p is prime and 10ⁿ-1 = 9 · R_n, it must divide either 9 or R_n.

• p cannot divide 9, since 9 = 10¹-1.

• Therefore p divides R_n.

• p cannot divide any R_k, since it doesn't divide 10^k-1 = 9 · R_k.

Therefore the p from Zsigmondy's Theorem is a novel prime factor of any R_n, n ≥ 2. ∎

---

An example of a repeated novel prime factor

The prime 487 is a repeated prime factor of R₄₈₆:

By the Fermat-Euler theorem, 10^487-1 ≡ 1 (mod 487). The order of 10 mod 487, that is, the smallest power of 10 that is 1 mod 487, therefore must be a divisor of 486. In fact, the order is equal to 486. It also happens that not only is 10⁴⁸⁶ ≡ 1 (mod 487), it's also 1 (mod 487²).

See here that the order of 10 mod 487 is 486; that is, that no smaller 10^k-1 is divisible by 487. Obviously, 487 doesn't divide 9, so it must divide R₄₈₆.

Answer 3

CJam, 18 bytes

{{)'1*imf}%W%:-_&}

Test it here.

Starting at 19 (the first repunit prime after 2) it will take a fairly long time.

Explanation

This is an unnamed block (CJam's equivalent of a function), which expects the input number n on the stack and leaves a list of prime factors instead:

{      e# Map this block over [0 1 ... n-1]...
  )'1* e#   Increment and create a string of that many 1s.
  i    e#   Convert to integer.
  mf   e#   Get its prime factors.
}%
W%     e# Reverse the list.
:-     e# Fold set difference onto the list, removing from the first list the elements of
       e# all other lists.
_&     e# Remove duplicates. Unfortunately, this necessary. Thomas Kwa found that the 486th
       e# repunit contains 487^2 (where 487 is a novel prime factor).

Answer 4

Haskell 86 bytes

import Data.Numbers.Primes
f n=[x|x<-primeFactors$div(10^n-1)9,notElem x$f=<<[1..n-1]]

Usage example: f 8 -> [73,137].

Takes a lot of time and memory for big n.

Direct implementation of the definition: take all prime factors x of Rn which do not show up before (f=<<[1..n-1] are all prime factors of R1 ... R(n-1)).

Answer 5

Mathematica 82 74 63 bytes

With 11 bytes saved thanks to alephalpha.

Complement@@Reverse@FactorInteger[(10^Range@#-1)/9][[;;,;;,1]]&

---

Prime factors of R70

(10^70 - 1)/9 = 1111111111111111111111111111111111111111111111111111111111111111111111

FactorInteger[(10^70 - 1)/9]

{{11, 1}, {41, 1}, {71, 1}, {239, 1}, {271, 1}, {4649, 1}, {9091, 1}, {123551, 1}, {909091, 1}, {4147571, 1}, {102598800232111471, 1}, {265212793249617641, 1}}

---

Novel prime factors of R70

Complement@@Reverse@FactorInteger[(10^Range@#-1)/9][[;;,;;,1]]&[70]

{4147571, 265212793249617641}

Answer 6

LabVIEW, 33 LabVIEW Primitives

19 takes forever...

Work by saving all Primes and deleting elements from the last set when they are found in the other array.

Answer 7

MATL, 25 bytes

This works for input up to 16:

10,i:^9/Y[t0)Yftb!w\~s1=)

The following version uses 31 bytes and works up to 18. For 19 it requires about 4 GB memory (I haven't been able to run it).

10,i:^9/Y[t0)5X2Y%Yfotb!w\~s1=)

Example

>> matl
 > 10,i:^1-,9/t0)5X2Y%Yfotb!w\~s1=)
 > 
> 6
7 13

Explanation

Consider for concreteness input 6. First the prime divisors of 111111 are computed; in this case the results are 3, 7, 11, 13, 37. Then the modulo operation (division remainder) is computed for all combinations of numbers 1, 11, ... 111111 and the computed divisors. This exploits MATL's implicit singleton expansion. The result is in this case a 6x5 matrix, with each column corresponding to one of the divisors. Accepted divisors (columns) are those for which only 1 value (namely the last) gives zero remainder.

10,i:^9/Y[   % generate vector with `1`, `11`, ... depending on input number, say "n"
t0)          % pick the last element: `111...1` (n ones)
5X2Y%        % * convert to uint64, so that larger numbers can be handled
Yf           % prime factors                                             
o            % * convert to double precision, so that modulus can be done
t            % duplicate                                                 
b            % bubble up element in stack                                
!            % transpose                                                 
w            % swap elements in stack                                    
\            % modulus after division (element-wise, singleton expansion)
~s           % number of zero values in each column
1=           % is equal to 1? (element-wise, singleton expansion)
)            % index divisors with that logical index

(*) Removed in short version

Answer 8

Julia, 103 bytes

R(n)=[keys(factor((10^n-1)÷9))...]
n->(r=R(n);isprime(r)?r:setdiff(r,reduce(vcat,[R(i)for i=1:n-1])))

This is an unnamed function that calls a helper function R. To call it, give the main function a name, e.g. f=n->....

Ungolfed:

function R(n::Integer)
    collect(keys(factor((10^n - 1) ÷ 9)))
end

function f(n::Integer)
    r = R(n)
    if isprime(r)
        r
    else
        setdiff(r, reduce(vcat, [R(i) for i = 1:n-1]))
    end
end

Answer 9

J, 24 bytes

[:({:-.}:)@:q:[:+/\10^i.

Expects extended-precision numerics after 6 (e.g. 19x instead of 19).

Try it online!

There's probably a shorter way to generate the repunits which avoids the caps, too.

Explanation

[: ({: -. }:) @: q: [: +/\ 10 ^ i.
                                i. Range [0, input)
                           10 ^    10 raised to the power of the range
                       +/\         Running sum of this list (list of repunits)
                 q:                Prime factors of the repunits
              @:                   Composed with
   ({: -. }:)                      Unique prime factors of last repunit
    {:                              Factors of last repunit (tail of matrix)
       -.                           Set subtraction with
          }:                        Rest of the matrix (curtail)

How it works, visually

I think that these sorts of visual explanations are easier to stomach for those who don't know J. These are results from the REPL.

   10 ^ i.6
1 10 100 1000 10000 100000

   +/\ 10 ^ i. 6
1 11 111 1111 11111 111111

   q: +/\ 10 ^ i. 6
 0   0  0  0  0
11   0  0  0  0
 3  37  0  0  0
11 101  0  0  0
41 271  0  0  0
 3   7 11 13 37

   ({: -. }:) q: +/\ 10 ^ i. 6
7 13