A038371 Smallest prime factor of 10^n + 1.

2, 11, 101, 7, 73, 11, 101, 11, 17, 7, 101, 11, 73, 11, 29, 7, 353, 11, 101, 11, 73, 7, 89, 11, 17, 11, 101, 7, 73, 11, 61, 11, 19841, 7, 101, 11, 73, 11, 101, 7, 17, 11, 29, 11, 73, 7, 101, 11, 97, 11, 101, 7, 73, 11, 101, 11, 17, 7, 101, 11, 73, 11, 101, 7, 1265011073

Offset: 0

Author

Miklos SZABO (mike(AT)ludens.elte.hu)

Keywords

• nonn

Comments

a(n) >= 7 for all n >= 1 since 10^n + 1 is then not divisible by 2, 3 or 5.

Record values are a({0, 1, 2, 16, 32, 64, ...}). - M. F. Hasler, Apr 04 2008

The record values (2, 11, 101, 353, 19841, 1265011073, ...) are also found in A185121 and A102050 (smallest prime factor of 10^2^n+1). - M. F. Hasler, Jun 28 2024

Examples

			a(12) = 73 as 10^12+1 = 1000000000001 = 73*137*99990001.
		

References

• Ehrhard Behrends, Five-Minute Mathematics, translated by David Kramer. American Mathematical Society (2008) p. 7

Links

• Max Alekseyev, Table of n, a(n) for n = 0..1023 (terms 0..500 from M. F. Hasler)
• Makoto Kamada, Factorizations of 100...001.

Crossrefs

Cf. A020639 (least prime factor), A062397 (10^n + 1), A003021 (largest prime factor of 10^n + 1), A057934 (number of prime factors of 10^n + 1, with multiplicity), A119704 (as before, without multiplicity), A185121 (smallest prime factor of 10^2^n+1), A102050 (as before, but 1 if 10^2^n+1 is prime).

Programs

Magma

[Min(PrimeFactors(10^n+1)):n in[0..70]]; // Vincenzo Librandi, Nov 08 2018

Mathematica

Table[FactorInteger[10^n + 1][[1, 1]], {n, 0, 49}] (* Alonso del Arte, Oct 21 2011 *)

PARI

A038371(n)=A020639(10^n+1) \\ Much more efficient than the naive {factor(10^n+1)[1,1]}. - M. F. Hasler, Apr 04 2008, edited Jun 29 2024

Formula

a(n) = A020639(A062397(n)).

For odd n, a(n) <= 11 since every (base 10) palindrome of even length is divisible by 11. - M. F. Hasler, Apr 04 2008 [See below for more precise formula.]

More generally, for k >= 0 and n == 2^k (mod 2^(k+1)), a(n) <= A185121(k) = (11, 101, 73, 17, 353, ...). This follows from x^{2q+1} + 1 = (x+1) Sum_{m=0..2q} (-x)^m, with x=10^2^k. - M. F. Hasler, Jul 30 2019

From M. F. Hasler, Jun 28 2024: (Start)

a(2k+1) = 7 iff k == 1 (mod 3), else 11. [Making the 2008 formula more precise.]

a(4k+2) = 29 iff k == 3 (mod 7), else = 61 if k == 7 (mod 15), else = 89 if k == 5 (mod 11), else 101.

a(8k+4) = 73 for all k >= 0.

a(16k+8) = 17 for all k >= 0.

a(32k+16) = 97 iff k==1 (mod 3), else 353.

a(64k+32) = 193 iff k==1 (mod 3), else 1217 if k==9 (mod 19), else 2753 if k==21 (mod 43), else 3137 if k==24 (mod 49), else 3329 if k==6 (mod 13), else 4481 if k==17 (mod 35), else 4673 if k==36 (mod 73), else 5953 if k==15 (mod 31), else 6529 if k==8 (mod 17), else 13633 if k==35 (mod 71), else 15937 if k==41 (mod 83), else 19841. (End)

Extensions

More terms from Reinhard Zumkeller, Mar 12 2002