A051953 -id:A051953 - cp's OEIS frontend

A053475 1 + the number of iterations of A051953 (Euler-cototient) function needed to reach 0, starting at n.

2, 3, 3, 4, 3, 5, 3, 5, 4, 6, 3, 6, 3, 6, 4, 6, 3, 7, 3, 7, 5, 7, 3, 7, 4, 7, 5, 7, 3, 8, 3, 7, 4, 8, 4, 8, 3, 8, 5, 8, 3, 9, 3, 8, 6, 8, 3, 8, 4, 9, 4, 8, 3, 9, 5, 8, 6, 9, 3, 9, 3, 8, 6, 8, 4, 9, 3, 9, 5, 9, 3, 9, 3, 9, 5, 9, 4, 10, 3, 9, 6, 10, 3, 10, 6, 9, 4, 9, 3, 10, 4, 9, 5, 9, 4, 9, 3, 9, 6, 10, 3, 10

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Analogous sequences of iteration-lengths for A000005 or A000010 are A036459 and A049108 resp. The length values of 3 occur if the initial value is prime resulting in {p,1,0} iterations.

			Starting with n=18, the iterations of A051953 are as follows: {18,12,8,4,2,1,0}. The length of this sequence is 7, so a(18) = 7. The function is applied a(n)-1 times.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000005, A000010, A051953, A036459, A049108, A076640.

Table[Length@ NestWhileList[# - EulerPhi@ # &, n, # > 0 &], {n, 84}] (* Michael De Vlieger, Jul 04 2016 *)

a(n) = A076640(n) + 1. - Michael De Vlieger, Jul 04 2016

A323410 Unitary analog of cototient function A051953: a(n) = n - A047994(n).

Original entry on oeis.org

0, 1, 1, 1, 1, 4, 1, 1, 1, 6, 1, 6, 1, 8, 7, 1, 1, 10, 1, 8, 9, 12, 1, 10, 1, 14, 1, 10, 1, 22, 1, 1, 13, 18, 11, 12, 1, 20, 15, 12, 1, 30, 1, 14, 13, 24, 1, 18, 1, 26, 19, 16, 1, 28, 15, 14, 21, 30, 1, 36, 1, 32, 15, 1, 17, 46, 1, 20, 25, 46, 1, 16, 1, 38, 27, 22, 17, 54, 1, 20, 1, 42, 1, 48, 21, 44, 31, 18, 1, 58, 19, 26, 33, 48

Offset: 1

Antti Karttunen, Jan 15 2019

Antti Karttunen, Table of n, a(n) for n = 1..21210
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A047994, A065463.

Cf. also A034460, A051953, A323409, A323413.

a[n_] := n - Times @@ (Power @@@ FactorInteger[n] - 1); a[1] = 0; Array[a, 100] (* Amiram Eldar, Apr 08 2023 *)

A047994(n) = { my(f=factor(n)~); prod(i=1, #f, f[1, i]^f[2, i]-1); };
A323410(n) = (n-A047994(n));

a(n) = n - A047994(n), where A047994 is unitary phi.

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - A065463 = 0.2955577... . - Amiram Eldar, Dec 15 2023

A063985 Partial sums of cototient sequence A051953.

Original entry on oeis.org

0, 1, 2, 4, 5, 9, 10, 14, 17, 23, 24, 32, 33, 41, 48, 56, 57, 69, 70, 82, 91, 103, 104, 120, 125, 139, 148, 164, 165, 187, 188, 204, 217, 235, 246, 270, 271, 291, 306, 330, 331, 361, 362, 386, 407, 431, 432, 464, 471, 501, 520, 548, 549, 585, 600, 632, 653, 683

Offset: 1

Labos Elemer, Sep 06 2001

nonn

Number of elements in the set {(x,y): 1 <= x <= y <= n, 1 = gcd(x,y)}; a(n) = A000217(n) - A002088(n) = A100613(n) - A185670(n). - Reinhard Zumkeller, Jan 21 2013

8*a(n) is the number of dots not in direct reach via a straight line from the center of a 2*n+1 X 2*n+1 array of dots. - Kiran Ananthpur Bacche, May 25 2022

Harry J. Smith, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A000010, A000217, A002088, A048290, A051953.

a063985 n = length [()| x <- [1..n], y <- [x..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013

// Save the file as A063985.java to compile and run
import java.util.stream.IntStream;
import java.util.*;
public class A063985 {
  public static int getInvisiblePoints(int n) {
    Set slopes = new HashSet();
    IntStream.rangeClosed(1, n).forEach(i ->
      {IntStream.rangeClosed(1, n).forEach(j ->
        slopes.add(Float.valueOf((float)i/(float)j))); });
    return (n * n - slopes.size() + n - 1) / 2;
  }
  public static void main(String args[]) throws Exception {
    IntStream.rangeClosed(1, 30).forEach(i ->
      System.out.println(getInvisiblePoints(i)));
  }
} // Kiran Ananthpur Bacche, May 25 2022

f[n_] := n(n + 1)/2 - Sum[ EulerPhi@i, {i, n}]; Array[f, 58] (* Robert G. Wilson v *)
Accumulate[Table[n-EulerPhi[n],{n,1,60}]] (* Harvey P. Dale, Aug 19 2015 *)

{ a=0; for (n=1, 1000, write("b063985.txt", n, " ", a+=n - eulerphi(n)) ) } \\ Harry J. Smith, Sep 04 2009

from sympy.ntheory import totient
def a(n): return sum(x - totient(x) for x in range(1,n + 1))
[a(n) for n in range(1, 51)] # Indranil Ghosh, Mar 18 2017

from functools import lru_cache
@lru_cache(maxsize=None)
def A063985(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(k1*(k1+1)-2*A063985(k1)-1)
        j, k1 = j2, n//j2
    return (2*n+c-j)//2 # Chai Wah Wu, Mar 24 2021

a(n) = Sum_{x=1..n} (x - phi(x)) = Sum(x) - Sum(phi(x)) = A000217(n) - A002088(n), phi(n) = A000010(n), cototient(n) = A051953(n).
a(n) = n^2 - A091369(n). - Enrique Pérez Herrero, Feb 25 2012
G.f.: x/(1 - x)^3 - (1/(1 - x))*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 18 2017
a(n) = (1/2 - 3/Pi^2)*n^2 + O(n*log(n)). - Amiram Eldar, Jul 26 2022

Corrected by Robert G. Wilson v, Dec 13 2006

A065385 Numbers m at which value of cototient function (A051953) reaches a new record: cototient(m) > cototient(k) for all k < m.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 102, 108, 114, 120, 126, 132, 138, 144, 150, 168, 180, 198, 204, 210, 240, 252, 264, 270, 294, 300, 330, 360, 378, 390, 420, 450, 462, 480, 504, 510, 540, 546, 570, 600, 630, 660, 690, 714

Offset: 1

Labos Elemer, Nov 05 2001

nonn

For totient values prime numbers give similar records.

			a(8) = 30 because for m = 1...29 the cototient values are all smaller than cototient(30) = 22 = A065386(8) and this is the 8th number at which such a record is reached; analogous sequences are A002093, A002182, A015702 or A005250 for functions other than cototient.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A051953, A065386.

With[{s = Array[# - EulerPhi@ # &, 10^3]}, Map[FirstPosition[s, #][[1]] &, Union@ FoldList[Max, s]]] (* Michael De Vlieger, May 16 2018 *)

r=-1; for(n=1,1000,d=n-eulerphi(n); if(r

{ n=0; x=-1; for (m=1, 10^9, c=m - eulerphi(m); if (c > x, x=c; write("b065385.txt", n++, " ", m); if (n==1000, return)) ) } \\ Harry J. Smith, Oct 17 2009

a=0; s=0; Do[s=n-EulerPhi[n]; If[s>a, a=s; Print[n]], {n, 1, 10000}]

A319700 a(n) = A051953(A252463(n)).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 4, 1, 1, 4, 4, 1, 3, 1, 6, 6, 1, 1, 8, 3, 1, 4, 8, 1, 7, 1, 8, 8, 1, 7, 12, 1, 1, 12, 12, 1, 9, 1, 12, 8, 1, 1, 16, 5, 5, 14, 14, 1, 9, 9, 16, 18, 1, 1, 22, 1, 1, 12, 16, 13, 13, 1, 18, 20, 11, 1, 24, 1, 1, 12, 20, 11, 15, 1, 24, 8, 1, 1, 30, 15, 1, 24, 24, 1, 21, 15, 24, 30, 1, 19, 32, 1, 7, 16, 30, 1, 19, 1, 28, 22

Offset: 1

Antti Karttunen, Nov 22 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A051953, A252463.

Cf. also A319699, A319703, A319989, A320107, A320111.

A051953(n) = (n - eulerphi(n));
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A252463(n) = if(!(n%2),n/2,A064989(n));
A319700(n) = A051953(A252463(n));

a(n) = A051953(A252463(n)).

A290087 a(1) = 0; for n > 1, a(n) = A289626(A051953(n)).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 5, 4, 5, 1, 5, 1, 5, 4, 5, 1, 8, 3, 4, 4, 8, 1, 6, 1, 8, 7, 4, 6, 13, 1, 8, 8, 13, 1, 8, 1, 13, 11, 13, 1, 17, 4, 8, 10, 11, 1, 11, 8, 17, 11, 8, 1, 18, 1, 17, 10, 17, 9, 12, 1, 11, 14, 12, 1, 21, 1, 10, 19, 21, 9, 10, 1, 21, 10, 11, 1, 21, 11, 18, 16, 21, 1, 18, 10, 21, 18, 21, 12, 25, 1, 28, 19, 21, 1, 19, 1, 28, 29

Offset: 1

Antti Karttunen, Aug 07 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A051953, A054571, A289626, A290086, A290085, A290086, A290088, A290089.

a(1) = 0; for n > 1, a(n) = A289626(A051953(n)).

A295885 Filter combining sum of proper divisors (A001065) and cototient (A051953) of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 5, 6, 1, 7, 1, 8, 9, 10, 1, 11, 1, 12, 13, 14, 1, 15, 16, 17, 18, 19, 1, 20, 1, 21, 22, 23, 24, 25, 1, 26, 27, 28, 1, 29, 1, 30, 31, 32, 1, 33, 34, 35, 36, 37, 1, 38, 27, 39, 40, 41, 1, 42, 1, 43, 44, 45, 46, 47, 1, 48, 49, 50, 1, 51, 1, 52, 53, 54, 46, 55, 1, 56, 57, 58, 1, 59, 40, 60, 61, 62, 1, 63, 36

Offset: 1

Antti Karttunen, Dec 03 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A001065, A051953, A291765.

allocatemem(2^30);
up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A051953(n) = (n-eulerphi(n));
A001065(n) = (sigma(n)-n);
Anotsubmitted5(n) = (1/2)*(2 + ((A051953(n)+A001065(n))^2) - A051953(n) - 3*A001065(n));
write_to_bfile(1,rgs_transform(vector(up_to,n,Anotsubmitted5(n))),"b295885.txt");

Restricted growth sequence transform of a(n) = (1/2)*(2 + ((A051953(n) + A001065(n))^2) - A051953(n) - 3*A001065(n)).

A300232 Restricted growth sequence transform of A286152, filter combining A051953(n) and A046523(n), cototient and the prime signature of n.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 5, 6, 7, 2, 8, 2, 9, 10, 11, 2, 12, 2, 12, 13, 14, 2, 15, 16, 17, 18, 19, 2, 20, 2, 21, 22, 23, 24, 25, 2, 26, 27, 28, 2, 29, 2, 30, 31, 32, 2, 33, 34, 35, 36, 37, 2, 38, 27, 39, 40, 41, 2, 42, 2, 43, 44, 45, 46, 47, 2, 48, 49, 47, 2, 50, 2, 51, 52, 53, 46, 54, 2, 55, 56, 57, 2, 58, 40, 59, 60, 61, 2, 62, 36, 63, 64, 65, 66, 67, 2, 68, 69

Offset: 1

Antti Karttunen, Mar 01 2018

nonn

			a(39) = a(55) (= 27) because both are nonsquare semiprimes (3*13 and 5*11), and both have cototient value 15 = 39 - phi(39) = 55 - phi(55).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A046523, A051953, A286152.

Cf. also A295885, A300223, A300224, A300226, A300229, A300230, A300231, A300233, A300235.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A051953(n) = (n - eulerphi(n));
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A286152(n) = (2 + ((A051953(n)+A046523(n))^2) - A051953(n) - 3*A046523(n))/2;
write_to_bfile(1,rgs_transform(vector(up_to,n,A286152(n))),"b300232.txt");

A300233 Filter sequence combining A051953(n) and A009194(n), cototient of n and gcd(n,sigma(n)).

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 5, 6, 7, 2, 8, 2, 9, 10, 11, 2, 12, 2, 13, 14, 13, 2, 15, 16, 17, 14, 18, 2, 19, 2, 20, 21, 22, 23, 24, 2, 25, 26, 27, 2, 28, 2, 29, 30, 31, 2, 32, 33, 34, 35, 36, 2, 37, 26, 38, 39, 40, 2, 41, 2, 42, 43, 44, 45, 46, 2, 47, 48, 49, 2, 50, 2, 51, 52, 53, 45, 54, 2, 55, 43, 56, 2, 57, 39, 58, 59, 60, 2, 61, 62, 60, 63, 55, 64, 65, 2, 66

Offset: 1

Antti Karttunen, Mar 01 2018

nonn

Restricted growth sequence transform of P(A051953(n), A009194(n)), where P(a,b) is a two-argument form of A000027 used as a Cantor pairing function N x N -> N.

			a(20) = a(22) (= 13) because A051953(20) = A051953(22) = 12 and A009194(20) = A009194(22) = 2.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A009194, A051953.

Cf. also A295885, A300223, A300226, A300229, A300230, A300231, A300232, A300235.

rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A009194(n) = gcd(n, sigma(n));
A051953(n) = (n - eulerphi(n));
Aux300233(n) = (1/2)*(2 + ((A051953(n)+A009194(n))^2) - A051953(n) - 3*A009194(n));
write_to_bfile(1,rgs_transform(vector(65537,n,Aux300233(n))),"b300233.txt");

A049586 a(n) is the GCD of the cototients (A051953) of n and n+1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 3, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 3, 3, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3

Offset: 0

Labos Elemer, Dec 28 2000

nonn

Most of the terms are 1.

Vincenzo Librandi, Table of n, a(n) for n = 0..5000

Cf. A000010, A051953, A058515.

[GCD((n+1-EulerPhi(n+1)), n-EulerPhi(n)): n in [1..100]]; // Vincenzo Librandi, Aug 10 2017

Map[GCD @@ Map[# - EulerPhi@ # &, #] &, Partition[Range@ 106, 2, 1]] (* Michael De Vlieger, Aug 09 2017 *)

a(n) = gcd(n + 1 - phi(n+1), n - phi(n)).

a(n) = gcd(A051953(n+1), A051953(n)).

cp's OEIS Frontend

A053475 1 + the number of iterations of A051953 (Euler-cototient) function needed to reach 0, starting at n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A323410 Unitary analog of cototient function A051953: a(n) = n - A047994(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A063985 Partial sums of cototient sequence A051953.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Java

Mathematica

PARI

Python

Python

Formula

Extensions

A065385 Numbers m at which value of cototient function (A051953) reaches a new record: cototient(m) > cototient(k) for all k < m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A319700 a(n) = A051953(A252463(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A290087 a(1) = 0; for n > 1, a(n) = A289626(A051953(n)).

Views

Author

Keywords

Links

Crossrefs

Formula

A295885 Filter combining sum of proper divisors (A001065) and cototient (A051953) of n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A300232 Restricted growth sequence transform of A286152, filter combining A051953(n) and A046523(n), cototient and the prime signature of n.

Views

Author

Keywords