A070306 -id:A070306 - cp's OEIS frontend

A115070 a(n) = phi(n)/3^b(n), where b(n) is #{primes p=1 mod 3 dividing n}.

1, 1, 2, 2, 4, 2, 2, 4, 6, 4, 10, 4, 4, 2, 8, 8, 16, 6, 6, 8, 4, 10, 22, 8, 20, 4, 18, 4, 28, 8, 10, 16, 20, 16, 8, 12, 12, 6, 8, 16, 40, 4, 14, 20, 24, 22, 46, 16, 14, 20, 32, 8, 52, 18, 40, 8, 12, 28, 58, 16, 20, 10, 12, 32, 16, 20, 22, 32, 44, 8, 70, 24, 24, 12, 40, 12, 20, 8, 26, 32, 54

Offset: 1

Steven Finch, Mar 01 2006

Cubic analog of A070306. Always an integer.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A000010, A005088, A070306, A060839, A115069.

with(numtheory):
a:= n-> phi(n)/3^add(`if`(irem(p, 3)=1, 1, 0), p=factorset(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 17 2019

b[n_] := Count[FactorInteger[n][[All, 1]], p_ /; Mod[p, 3] == 1]; b[1] = 0;
a[n_] := EulerPhi[n]/3^b[n];
Table[a[n], {n, 1, 81}] (* Jean-François Alcover, Feb 17 2019 *)
f[p_, e_] := (p - 1)*p^(e - 1)/If[Mod[p, 3] == 1, 3, 1]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 30 2024 *)

{b(n)=my(f=factor(n)[, 1]); sum(i=1, #f, f[i]%3==1)};
{a(n)= eulerphi(n)/3^b(n)};
vector(80, n, a(n)) \\ G. C. Greubel, Feb 17 2019

a(n) = {my(f = factor(n)); prod(i = 1, #f~, (f[i,1]-1)*f[i,1]^(f[i,2]-1)/if(f[i,1] % 3 == 1, 3,1));} \\ Amiram Eldar, Nov 30 2024

From Amiram Eldar, Nov 30 2024: (Start)
a(n) = A000010(n)/3^A005088(n) = A000010(n)/A115069(n).
Multiplicative with a(p^e) = (p-1)*p^(e-1)/3 if p == 1 (mod 3), and (p-1)*p^(e-1) otherwise. (End)

a(1)=1 prepended by Alois P. Heinz, Feb 17 2019

Keyword mult added by Amiram Eldar, Nov 30 2024

A365687 a(n) = number of fractions m/n, 0 <= m < n, gcd(m,n) = 1 whose partial fraction decomposition has integer part 0.

Original entry on oeis.org

1, 1, 2, 2, 4, 1, 6, 4, 6, 2, 10, 2, 12, 3, 4, 8, 16, 3, 18, 4, 6, 5, 22, 4, 20, 6, 18, 6, 28, 0, 30, 16, 10, 8, 12, 6, 36, 9, 12, 8, 40, 1, 42, 10, 12, 11, 46, 8, 42, 10, 16, 12, 52, 9, 20, 12, 18, 14, 58, 2, 60, 15, 18, 32, 24, 1, 66, 16, 22, 2, 70, 12, 72, 18, 20

Offset: 1

William P. Orrick, Sep 15 2023

nonn

If n = p_1^r_1 p_2^r_2 ... p_k^r_k where p_1, ..., p_k are distinct primes, the partial fraction decomposition of m/n has the form z + Sum_{i=1..k} a_i / p_i^r_i = z + Sum_{i=1..k} Sum_{j=1..r_i} a_ij / p_i^j where 0 < a_i < p_i^r_i, gcd(a_i,p_i) = 1, and where 0 <= a_ij < p_i (a_ij > 0 when j = r_i). z is the integer part.
If 0 < m / n < 1 and gcd(m,n) = 1 then the integer part satisfies 1 - k <= z <= 0.
If n is a nonhyperbolic number, which means that Sum_{i=1..k} 1 / p_i^r_i >= 1, then the integer part is not zero for any m/n with 0 < m / n < 1, gcd(m,n) = 1.
Assuming gcd(m,n) = 1, if m/n has integer part z then (n - m)/n has integer part 1 - k - z. This means there are equally many reduced fractions with denominator n > 1 between 0 and 1 having integer part z and integer part 1 - k - z.

			a(10) = 2 because, of the four nonnegative reduced fractions less than 1 with denominator 10, two of them (7/10 and 9/10) have integer part 0:
   1/10 = -1 + 1/2 + 3/5
   3/10 = -1 + 1/2 + 4/5
   7/10 = 1/2 + 1/5
   9/10 = 1/2 + 2/5.

Cf. A070306, A181629, A028236.

def a(n):
    b = n
    fs = factor(b)
    # bzList will hold Bezout coefficients to express 1/n as combination
    # of the reciprocals of the prime power factors of n. ppList will
    # hold the prime power factors themselves.
    bzList = []
    bz0 = 1
    ppList = []
    for f in fs:
        q = f[0]^f[1]
        ppList.append(q)
        b = b / q
        bzThis = xgcd(q,b)
        bzList.append(bz0*bzThis[2])
        bz0 = bz0 * bzThis[1]
    ct = 0
    for j in n.coprime_integers(n):
        if sum(floor(j*bzList[i]/ppList[i])\
         for i in range(len(ppList))) == 0:
            ct = ct + 1
    return(ct)

a(n) = phi(n) if n is a prime power.
a(n) = phi(n) / 2 if n is the product of powers of two distinct primes.
a(n) = 0 if n is in A181629, that is, if n is a nonhyperbolic number.
a(n) = A070306(n) if n is a prime power or a product of powers of two distinct primes.

cp's OEIS Frontend

A115070 a(n) = phi(n)/3^b(n), where b(n) is #{primes p=1 mod 3 dividing n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions