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,1

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

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

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 *)

Prog

(PARI) a(n)=if(n<1, 0, !isprime(n)) /* Michael Somos, Jun 08 2005 */
(Haskell)
a005171 = (1 -) . a010051  -- Reinhard Zumkeller, Mar 30 2014
(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

Crossrefs

Cf. A010051, A018252, A023890.

Cf. A157423, A157424, A052284, A050374.

Sequence in context: A242252 A100810 A174889 * A283265 A365410 A181406

Adjacent sequences: A005168 A005169 A005170 * A005172 A005173 A005174

Keyword

nonn,easy

Author

Russ Cox

Status

approved