A100371 a(n) = 2^phi(n) - 1 = A066781(n) - 1.

1, 1, 3, 3, 15, 3, 63, 15, 63, 15, 1023, 15, 4095, 63, 255, 255, 65535, 63, 262143, 255, 4095, 1023, 4194303, 255, 1048575, 4095, 262143, 4095, 268435455, 255, 1073741823, 65535, 1048575, 65535, 16777215, 4095, 68719476735, 262143, 16777215, 65535

Offset: 1

Author

Labos Elemer, Nov 30 2004

Keywords

• easy
• nonn

Comments

Number of nonempty subsets of reduced residue system [RRS(n)] modulo n.

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• N. Bliss, B. Fulan, S. Lovett, and J. Sommars, Strong Divisibility, Cyclotomic Polynomials, and Iterated Polynomials, Amer. Math. Monthly, 120 (2013), 519-536.

Crossrefs

Cf. A000010, A066781.

Programs

Maple

A100371:=n->2^numtheory[phi](n)-1: seq(A100371(n), n=1..60); # Wesley Ivan Hurt, Apr 14 2017

Mathematica

Table[2^EulerPhi[n] - 1, {n, 1, 50}]

PARI

a(n) = 2^eulerphi(n) - 1; \\ Michel Marcus, Apr 14 2017

Python

from sympy import totient
def a(n): return 2**totient(n) - 1 # Indranil Ghosh, Apr 14 2017

Formula

a(n) = Sum_{i=1..n} binomial(phi(n), i). - Enrique Pérez Herrero, Mar 10 2012

Extensions

Entry revised by N. J. A. Sloane, Jun 07 2013