A005171 Characteristic function of nonprimes: 0 if n is prime, else 1.

1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1

Offset: 1

Author

Russ Cox

Keywords

• nonn
• easy

Comments

Number of orbits of length n in map whose periodic points are A023890. - Thomas Ward

Characteristic function of nonprimes A018252. - Jonathan Vos Post, Dec 30 2007

Triangle A157423 = A005171 in every column. A052284 = INVERT transform of A005171, and the eigensequence of triangle A157423. - Gary W. Adamson, Feb 28 2009

References

• Douglas Hofstadter, Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
• Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
• Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.
• Index entries for characteristic functions

Crossrefs

Cf. A010051, A018252, A023890.

Cf. A157423, A157424, A052284, A050374, A033273, A008683.

Programs

Haskell

a005171 = (1 -) . a010051  -- Reinhard Zumkeller, Mar 30 2014

Maple

A005171 := proc(n)
    if isprime(n) then
        0 ;
    else
        1 ;
    end if;
end proc: # R. J. Mathar, May 26 2017

Mathematica

a[n_] := If[PrimeQ@ n, 0, 1]; Array[a, 105] (* Robert G. Wilson v, Jun 20 2011 *)
nn = 105; t[n_, k_] :=  t[n, k] = If[n == k, 1, If[k == 1, 1 - Product[t[n, k + i], {i, 1, n - 1}], If[Mod[n, k] == 0, t[n/k, 1], 1], 1]]; Table[t[n, 1], {n, 1, nn}] (* Mats Granvik, Sep 21 2013 *)

PARI

a(n)=if(n<1, 0, !isprime(n)) /* Michael Somos, Jun 08 2005 */

Python

from sympy import isprime
def a(n): return int(not isprime(n))
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Oct 28 2021

Formula

a(n) = (1/n)* Sum_{ d divides n } mu(d)*A023890(n/d). E.g., a(6) = 1 since the 6th term of A023890 is 7 and the first term is 1. [edited by Michel Marcus, Dec 14 2023]

a(n) = 1 - A010051(n). - Jonathan Vos Post, Dec 30 2007

a(n) equals the first column in a table T defined by the recurrence: If n = k then T(n,k) = 1 else if k = 1 then T(n,k) = 1 - Product_{k divides n} of T(n,k), else if k divides n then T(n,k) = T(n/k,1). This is true since T(n,k) = 0 when k divides n and n/k is prime which results in Product_{k divides n} = 0 for the composite numbers and where k ranges from 2 to n. Therefore there is a remaining 1 in the expression 1-Product_{k divides n}, in the first column. Provided below is a Mathematica program as an illustration. - Mats Granvik, Sep 21 2013

a(n) = A057427(A239968(n)). - Reinhard Zumkeller, Mar 30 2014

a(n) = Sum_{d|n} A033273(d)*A008683(n/d). - Ridouane Oudra, Jul 03 2025