A139555 - OEIS

A139555

a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.

1, 1, 2, 2, 4, 2, 5, 4, 6, 4, 8, 4, 9, 6, 7, 7, 11, 6, 12, 8, 10, 8, 13, 8, 13, 10, 13, 11, 16, 8, 17, 14, 15, 13, 16, 11, 19, 14, 16, 13, 20, 12, 21, 16, 17, 16, 22, 15, 22, 17, 20, 18, 24, 17, 22, 18, 21, 19, 25, 16, 26, 21, 22, 22, 25, 18, 28, 22, 25, 19, 29, 21, 30, 24, 26, 24

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Indices of first occurrence of each natural number: 1, 3, 5, 7, 9, 15, 11, 13, 21, 17, 19, 23, 32, 33, ..., . - Robert G. Wilson v, May 12 2008

From Reinhard Zumkeller, Oct 27 2010: (Start)

a(n) <= A000010(n); a(A051250(n)) = A000010(A051250(n)), 1 <= n <= 17.

Conjecture: a(n) < A000010(n) for n > 60, cf. A051250. (End)

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

FORMULA

a(n) = Sum_{k=1..A000010(n)} A010055(A038566(n,k)). - Reinhard Zumkeller, Feb 23 2012

a(n) = A073093(A038610(n)). - Ridouane Oudra, Jan 20 2026

a(n) = A065515(n) - A361373(n). - Ridouane Oudra, Jan 22 2026

EXAMPLE

All the positive integers <= 21 that are coprime to 21 are 1,2,4,5,8,10,11,13,16,17,19,20. Of these integers, only 1,2,4,5,8,11,13,16,17,19 are prime-powers. There are 10 of these prime-powers; so a(21) = 10.

MAPLE

isA000961 := proc(n) if n = 1 or isprime(n) then true; else RETURN(nops(ifactors(n)[2]) =1) ; fi ; end: A139555 := proc(n) local a, i; a := 0 ; for i from 1 to n do if isA000961(i) and gcd(i, n) = 1 then a := a+1 ; fi ; od: a ; end: seq(A139555(n), n=1..100) ; # R. J. Mathar, May 12 2008

MATHEMATICA

f[n_] := Length@ Select[Range@ n, Length@ FactorInteger@ # == 1 == GCD[n, # ] &]; Array[f, 76] (* Robert G. Wilson v, May 12 2008 *)

PROG

(Haskell)

a139555 = sum . map a010055 . a038566_row

-- Reinhard Zumkeller, Feb 23 2012, Oct 27 2010

CROSSREFS

Cf. A000010, A010055, A038566, A051250, A139556.

Cf. A065515. - Reinhard Zumkeller, Oct 27 2010

Cf. A073093, A038610, A361373.

Sequence in context: A243271 A232245 A121895 * A241814 A088371 A133181

Adjacent sequences: A139552 A139553 A139554 * A139556 A139557 A139558