A121719 Strings of digits which are composite regardless of the base in which they are interpreted. Exclude bases in which numbers are not interpretable.

4, 6, 8, 9, 20, 22, 24, 26, 28, 30, 33, 36, 39, 40, 42, 44, 46, 48, 50, 55, 60, 62, 63, 64, 66, 68, 69, 70, 77, 80, 82, 84, 86, 88, 90, 93, 96, 99, 100, 110, 112, 114, 116, 118, 120, 121, 130, 132, 134, 136, 138, 140, 143, 144

Offset: 1

Author

Tanya Khovanova, Sep 08 2006

Keywords

• nonn
• easy
• base

Comments

Comments from Franklin T. Adams-Watters:

"Think of these as polynomials. E.g. 121 is the polynomial n^2+2n+1. There are three cases:

"(1) If the coefficients (digits) all have a common factor, the result will be divisible by that factor.

"(2) If the polynomial can be factored, the numbers will be composite. n^2+2n+1 = (n+1)^2, so it is always composite.

"(3) Otherwise, look at the polynomial modulo primes up to its degree. For example, 112 (n^2+n+2, degree 2) modulo 2 is always 0, so it is always divisible by 2.

"Note that condition (1) is really a special case of condition (2), where one of the factors is a constant.

"If none of the above conditions apply, the polynomial will (probably) have prime values."

From Iain Fox, Sep 02 2020: (Start)

lim_{k->infinity} (1/k)*Sum_{i=1..k} a_c(i) > .3 if it exists, where a_c(n) is the characteristic function of a(n) (1 if n is in a(n), otherwise 0).

If the Bunyakovsky conjecture is true, the list of reasons a number is in this sequence detailed by Franklin T. Adams-Watters above is a complete list.

If the Bunyakovsky conjecture and the Extended Riemann Hypothesis are true, the above limit equals 4340435807/13235512500 = 0.3279386... (proof by Ravi Fernando in link by Iain Fox).

All members of A008592 except 1 and 10 are in this sequence.

(End)

Examples

			String 55 in every base in which it is interpretable is divisible by 5. String 1001 in base a is divisible by a+1. Hence 55 and 1001 both belong to this sequence.
		

Links

• Iain Fox, Table of n, a(n) for n = 1..10000
• Iain Fox, What percentage of positive integers, written in base 10, are composite regardless of what base they are interpreted in?, Math StackExchange, September 2020.
• Ed Pegg, Jr., Bouniakowsky Conjecture.
• Eric W. Weisstein, Extended Riemann Hypothesis.
• Wikipedia, Bunyakovsky conjecture.
• Wikipedia, Generalized Riemann Hypothesis.

Crossrefs

Supersequence: A002808.

Cf. A008592, A267509.

Programs

PARI

is(n)=if(n<10, return(!isprime(n)&&n>1)); if(content(n=digits(n))>1, return(1)); if(vecsum(factor(n*=vectorv(#n, i, x^(#n-i)))[,2])>1, return(1)); forprime(p=2, #n-1, for(x=1, p, if(eval(n)%p, next(2))); return(1)); for(x=vecmax(Vec(n))+1, +oo, if(isprime(eval(n)), return(0))) \\ Iain Fox, Aug 31 2020

Extensions

More terms from Franklin T. Adams-Watters, Sep 12 2006