A007015 -id:A007015 - cp's OEIS frontend

A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).

0, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3

Offset: 0

Felix Weinstein (wain(AT)ana.unibe.ch) and Clark Kimberling

Also number of 0's (or B's) in the Wythoff representation of n -- see the Reble link. See also A135817 for references and links for the Wythoff representation for n >= 1. - Wolfdieter Lang, Jan 21 2008; N. J. A. Sloane, Jun 28 2008
Or, a(n) is the number of applications of Wythoff's B sequence A001950 needed in the unique Wythoff representation of n >= 1. E.g., 16 = A(B(A(A(B(1))))) = ABAAB = `10110`, hence a(16) = 2. - Wolfdieter Lang, Jan 21 2008
Let M(0) = 0, M(1) = 1 and for i > 0, M(i+1) = f(concatenation of M(j), j from 0 to i - 1) where f is the morphism f(k) = k + 1. Then the sequence is the concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003
From Joerg Arndt, Nov 09 2012: (Start)
Let m be the number of parts in the listing of the compositions of n into odd parts as lists of parts in lexicographic order, a(k) = (n - length(composition(k)))/2 for all k < Fibonacci(n) and all n (see example).
Let m be the number of parts in the listing of the compositions of n into parts 1 and 2 as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < Fibonacci(n) and all n (see example).
A000120 gives the equivalent for (all) compositions. (End)
a(n) = A104324(n) - A213911(n); row lengths in A035516 and A035516. - Reinhard Zumkeller, Mar 10 2013
a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - Alan Worley, Apr 17 2015
This follows from the fact that the sequence is subadditive: a(n+m) <= a(n) + a(m) for nonnegative integers n,m.  See Lemma 2.1 of the Stoll link. - Robert Israel, Apr 17 2015
From Michel Dekking, Mar 08 2020: (Start)
This sequence is a morphic sequence on an infinite alphabet, i.e., (a(n)) is a letter-to-letter projection of a fixed point of a morphism tau.
The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
      tau((j,0)) = (j,0) (j+1,1),
      tau((j,1)) = (j,0).
The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
This implies that for all n and j one has
      |tau^n(j,0)| = F(n+2),
where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
Secondly, we need the following simple, but crucial observation. Let the  Zeckendorf representation of n be Z(n) = A014417(n). For example,
     Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
      Z(F(n+1)+i) = 10...0 Z(i),
where zeros are added to Z(i) to give the total representation length n-1.
This gives for i = 0,1,...,F(n)-1 that
      a(F(n+1)+i) = a(i) + 1.
From the first observation follows that the first F(n+1) letters of tau^n(j,0) are equal to tau^{n-1}(j,0), and the last F(n) letters of tau^n(j,0) are equal to tau^{n-1}(j+1,1) = tau^{n-2}(j+1,0).
Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
It is of course possible to obtain a morphism tau' on the natural numbers by changing the alphabet:  (j,0)-> 2j  (j,1)-> 2j+1, which yields the morphism
      tau'(2j) = 2j, 2j+3,  tau'(2j+1) = 2j.
The fixed point of tau' starting with 0 is
      u = 03225254254472544747625...
The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
(End)

			a(46) = a(1 + 3 + 8 + 34) = 4.
From _Joerg Arndt_, Nov 09 2012: (Start)
Connection to the compositions of n into odd parts (see comment):
[ #]:  a(n)  composition into odd parts
[ 0]   [ 0]   1 1 1 1 1 1 1 1
[ 1]   [ 1]   1 1 1 1 1 3
[ 2]   [ 1]   1 1 1 1 3 1
[ 3]   [ 1]   1 1 1 3 1 1
[ 4]   [ 2]   1 1 1 5
[ 5]   [ 1]   1 1 3 1 1 1
[ 6]   [ 2]   1 1 3 3
[ 7]   [ 2]   1 1 5 1
[ 8]   [ 1]   1 3 1 1 1 1
[ 9]   [ 2]   1 3 1 3
[10]   [ 2]   1 3 3 1
[11]   [ 2]   1 5 1 1
[12]   [ 3]   1 7
[13]   [ 1]   3 1 1 1 1 1
[14]   [ 2]   3 1 1 3
[15]   [ 2]   3 1 3 1
[16]   [ 2]   3 3 1 1
[17]   [ 3]   3 5
[18]   [ 2]   5 1 1 1
[19]   [ 3]   5 3
[20]   [ 3]   7 1
Connection to the compositions of n into parts 1 or 2 (see comment):
[ #]:  a(n)  composition into parts 1 and 2
[ 0]   [0]   1 1 1 1 1 1 1
[ 1]   [1]   1 1 1 1 1 2
[ 2]   [1]   1 1 1 1 2 1
[ 3]   [1]   1 1 1 2 1 1
[ 4]   [2]   1 1 1 2 2
[ 5]   [1]   1 1 2 1 1 1
[ 6]   [2]   1 1 2 1 2
[ 7]   [2]   1 1 2 2 1
[ 8]   [1]   1 2 1 1 1 1
[ 9]   [2]   1 2 1 1 2
[10]   [2]   1 2 1 2 1
[11]   [2]   1 2 2 1 1
[12]   [3]   1 2 2 2
[13]   [1]   2 1 1 1 1 1
[14]   [2]   2 1 1 1 2
[15]   [2]   2 1 1 2 1
[16]   [2]   2 1 2 1 1
[17]   [3]   2 1 2 2
[18]   [2]   2 2 1 1 1
[19]   [3]   2 2 1 2
[20]   [3]   2 2 2 1
(End)
From _Michel Dekking_, Mar 08 2020: (Start)
The third iterate of the morphism tau generating this sequence:
      tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
= (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)

Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
F. Weinstein, The Fibonacci Partitions, preprint, 1995.
Édouard Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

T. D. Noe, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook), pp. 754-756.
Paul Baird-Smith, Alyssa Epstein, Kristen Flint, and Steven J. Miller, The Zeckendorf Game, arXiv:1809.04881 [math.NT], 2018.
D. E. Daykin, Representation of natural numbers as sums of generalized Fibonacci numbers, J. London Math. Soc. 35 (1960) 143-160.
Michel Dekking, Points of increase of the sum of digits function of the base phi expansion, arXiv:2003.14125 [math.CO], 2020.
F. Michel Dekking, The sum of digits functions of the Zeckendorf and the base phi expansions, Theoretical Computer Science (2021) Vol. 859, 70-79.
Damien Jamet, Pierre Popoli, and Thomas Stoll, Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences, arXiv:2106.09959 [math.NT], 2021, see p. 5.
C. G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Stichting Mathematisch Centrum, Zuivere Wiskunde, 1951.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See p. 10.
I. Nemes, Fibonacci representations of multiples of Fibonacci numbers.
Don Reble, Zeckendorf vs. Wythoff representations: Comments on A007895.
Thomas Stoll, Combinatorial constructions for the Zeckendorf sum of digits of polynomial values, The Ramanujan Journal November 2013, Volume 32, Issue 2, pp 227-243.
F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT], 2003-2018.

Cf. A000045, A007953, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911, A014417, A003849.
Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
Record positions are in A027941.

a007895 = length . a035516_row  -- Reinhard Zumkeller, Mar 10 2013

# With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n.
with(combinat): B := proc (n) local A, ct, m, j: A := proc (n) local i: for i while fibonacci(i) <= n do n-fibonacci(i) end do end proc: ct := 0; m := n: for j while 0 < A(m) do ct := ct+1: m := A(m) end do: ct+1 end proc: 0, seq(B(n), n = 1 .. 104);
# Emeric Deutsch, Jul 05 2010
N:= 1000: # to get a(n) for n <= N
m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)):
Z:= Vector(m):
a[0]:= 0:
for n from 1 to N do
if Z[1] = 0 then Z[1]:= 1; q:= 1;
else Z[2]:= 1; Z[1]:= 0; q:= 2;
fi;
while Z[q+1] = 1 do
  Z[q]:= 0;
  Z[q+1]:= 0;
  Z[q+2]:= 1;
  q:= q+2;
od:
a[n]:= add(Z[i],i=1..m);
od:
seq(a[n],n=0..N); # Robert Israel, Apr 17 2015
# alternative
read("transforms") : # https://oeis.org/transforms.txt
A007895 := proc(n)
    wt(A003714(n)) ;
end proc:
seq(A007895(n),n=0..10) ; # R. J. Mathar, Sep 22 2020

zf[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); zeckRep[n_] := If[n == 0, 0, r = n; s = {}; fr = zf[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]; zeckRepLen[n_] := Length[zeckRep[n]]; Table[zeckRepLen[n], {n, 0, 104}] (* Jean-François Alcover, Sep 27 2011 *)
DigitCount[Select[Range[0, 1000], BitAnd[#, 2#] == 0 &], 2, 1] (* Jean-François Alcover, Jan 25 2018 *)
Table[Length[DeleteCases[NestWhileList[# - Fibonacci[Floor[Log[Sqrt[5] * # + 3/2]/Log[GoldenRatio]]] &, n, # > 1 &], 0]], {n, 0, 143}] (* Alonso del Arte, May 14 2019 *)
Flatten[Nest[{Flatten[#], #[[1]] + 1} &, {0, 1}, 9]] (* Paolo Xausa, Jun 17 2024 *)

a(n,mx=0)=if(n<4,n>0,if(!mx,while(fibonacci(mx)n,mx--); 1+a(n-fibonacci(mx),mx-2)) \\ Charles R Greathouse IV, Feb 14 2013

a(n)=if(n<4, n>0, my(k=2,s,t); while(fibonacci(k++)<=n,); while(k && n, t=fibonacci(k); if(t<=n, n-=t; s++); k--); s) \\ Charles R Greathouse IV, Sep 02 2015

from sympy import fibonacci
def a(n):
    k=0
    x=0
    while n>0:
        k=0
        while fibonacci(k)<=n: k+=1
        x+=10**(k - 3)
        n-=fibonacci(k - 1)
    return str(x).count("1")
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 09 2017

a(n) = A000120(A003714(n)). - Reinhard Zumkeller, May 05 2005
a(n) = A107015(n) + A107016(n). - Reinhard Zumkeller, May 09 2005
a(n) = A143299(n+1) - 1. - Filip Zaludek, Oct 31 2016
a(n) = A007953(A014417(n)). - Amiram Eldar, Oct 10 2023

Edited by N. J. A. Sloane Jun 27 2008 at the suggestion of R. J. Mathar and Don Reble

A005277 Nontotients: even numbers k such that phi(m) = k has no solution.

Original entry on oeis.org

14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, 302, 304, 308, 314, 318

Offset: 1

N. J. A. Sloane

nonn

If p is prime then the following two statements are true. I. 2p is in the sequence iff 2p+1 is composite (p is not a Sophie Germain prime). II. 4p is in the sequence iff 2p+1 and 4p+1 are composite. - Farideh Firoozbakht, Dec 30 2005
Another subset of nontotients consists of the numbers j^2 + 1 such that j^2 + 2 is composite. These numbers j are given in A106571. Similarly, let b be 3 or a number such that b == 1 (mod 4). For any j > 0 such that b^j + 2 is composite, b^j + 1 is a nontotient. - T. D. Noe, Sep 13 2007
The Firoozbakht comment can be generalized: Observe that if k is a nontotient and 2k+1 is composite, then 2k is also a nontotient. See A057192 and A076336 for a connection to Sierpiński numbers. This shows that 271129*2^j is a nontotient for all j > 0. - T. D. Noe, Sep 13 2007

			There are no values of m such that phi(m)=14, so 14 is a term of the sequence.

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 44 at p. 91.
R. K. Guy, Unsolved Problems in Number Theory, B36.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 91.

Robert G. Wilson v, Table of n, a(n) for n = 1..29750 (terms 1..10000 from T. D. Noe).
Lambert A'Campo, Every 7-Dimensional Abelian Variety over the p-adic Numbers has a Reducible L-adic Galois Representation, arXiv:2006.06737 [math.NT], 2020.
Matteo Caorsi and Sergio Cecotti, Geometric classification of 4d N=2 SCFTs, arXiv:1801.04542 [hep-th], 2018.
K. Ford, S. Konyagin, and C. Pomerance, Residue classes free of values of Euler's function, arXiv:2005.01078 [math.NT] (1999).
L. Havelock, A Few Observations on Totient and Cototient Valence.
Eric Weisstein's World of Mathematics, Nontotient.
Wikipedia, Nontotient.
Robert G. Wilson v, Letter to N. J. A. Sloane, Jul. 1992.

See A007617 for all numbers k (odd or even) such that phi(m) = k has no solution.
All even numbers not in A002202. Cf. A000010.
Cf. A005384, A006093, A014197, A057192, A076336, A079695, A106571.

a005277 n = a005277_list !! (n-1)
a005277_list = filter even a007617_list
-- Reinhard Zumkeller, Nov 22 2015

[n: n in [2..400 by 2] | #EulerPhiInverse(n) eq 0]; // Marius A. Burtea, Sep 08 2019

A005277 := n -> if type(n,even) and invphi(n)=[] then n fi: seq(A005277(i),i=1..318); # Peter Luschny, Jun 26 2011

searchMax = 320; phiAnsYldList = Table[0, {searchMax}]; Do[phiAns = EulerPhi[m]; If[phiAns <= searchMax, phiAnsYldList[[phiAns]]++ ], {m, 1, searchMax^2}]; Select[Range[searchMax], EvenQ[ # ] && (phiAnsYldList[[ # ]] == 0) &] (* Alonso del Arte, Sep 07 2004 *)
totientQ[m_] := Select[ Range[m +1, 2m*Product[(1 - 1/(k*Log[k]))^(-1), {k, 2, DivisorSigma[0, m]}]], EulerPhi[#] == m &, 1] != {}; (* after Jean-François Alcover, May 23 2011 in A002202 *) Select[2 Range@160, ! totientQ@# &] (* Robert G. Wilson v, Mar 20 2023 *)

is(n)=n%2==0 && !istotient(n) \\ Charles R Greathouse IV, Mar 04 2017

a(n) = 2*A079695(n). - R. J. Mathar, Sep 29 2021

{k: k even and A014197(k) = 0}. - R. J. Mathar, Sep 29 2021

More terms from Jud McCranie, Oct 13 2000

A005114 Untouchable numbers, also called nonaliquot numbers: impossible values for the sum of aliquot parts function (A001065).

Original entry on oeis.org

2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248, 262, 268, 276, 288, 290, 292, 304, 306, 322, 324, 326, 336, 342, 372, 406, 408, 426, 430, 448, 472, 474, 498, 516, 518, 520, 530, 540, 552, 556, 562, 576, 584, 612, 624, 626, 628, 658

Offset: 1

N. J. A. Sloane

Complement of A078923. - Lekraj Beedassy, Jul 19 2005
Chen & Zhao show that the lower density of this sequence is at least 0.06, improving on te Riele. - Charles R Greathouse IV, Dec 28 2013
Numbers k such that A048138(k) = 0. A048138(k) measures how "touchable" k is. - Jeppe Stig Nielsen, Jan 12 2020
From Amiram Eldar, Feb 13 2021: (Start)
The term "untouchable number" was coined by Alanen (1972). He found the 570 terms below 5000.
Erdős (1973) proved that the lower asymptotic density of untouchable numbers is positive, te Riele (1976) proved that it is > 0.0324, and Banks and Luca (2004, 2005) proved that it is > 1/48.
Pollack and Pomerance (2016) conjectured that the asymptotic density is ~ 0.17. (End)
The upper asymptotic density is less than 1/2 by the 'almost all' binary Goldbach conjecture, independently proved by Nikolai Chudakov, Johannes van der Corput, and Theodor Estermann. (In this context, this shows that the density of the odd numbers of this form is 0 (consider A001065(p*q) for prime p, q); full Goldbach would prove that 5 is the only odd number in this sequence.) - Charles R Greathouse IV, Dec 05 2022

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer, 2004, section B10, pp. 100-101.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 65.
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, page 93.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 147.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 125.

Giovanni Resta, Table of n, a(n) for n = 1..13863 (terms < 10^5; first 8153 terms from Klaus Brockhaus)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 840.
Jack David Alanen, Empirical study of aliquot series, Ph.D Thesis, Yale University, 1972.
William D. Banks and Florian Luca, Noncototients and Nonaliquots, arXiv:math/0409231 [math.NT], 2004.
William D. Banks and Florian Luca, Nonaliquots and Robbins numbers, Colloq. Math., Vol. 103, No. 1 (2005), pp. 27-32.
Yong-Gao Chen and Qing-Qing Zhao, Nonaliquot numbers, Publ. Math. Debrecen, Vol. 78, No. 2 (2011), pp. 439-442.
K. Chum, R. K. Guy, M. J. Jacobson, Jr., and A. S. Mosunov, Numerical and statistical analysis of aliquot sequences, Experimental Mathematics (2018), pp. 1-12.
Paul Erdős, Über die Zahlen der Form sigma(n)-n und n-phi(n), Elemente der Math., Vol. 28 (1973), pp. 83-86; alternative link (in German).
Shyam Sunder Gupta, Beauty of Number 153, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 15, 399-410.
Victor Meally, Letter to N. J. A. Sloane, no date.
Paul Pollack, Not Always Buried Deep: A Second Course in Elementary Number Theory, AMS, 2009, p. 272.
Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, For Richard Guy on his 99th birthday: May his sequence be unbounded, Trans. Amer. Math. Soc. Ser. B, Vol. 3 (2016), pp. 1-26; Errata.
Carl Pomerance and Hee-Sung Yang, On untouchable numbers and related problems, 2012.
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp., Vol. 83, No. 288 (2014), pp. 1903-1913; alternative link.
Giovanni Resta, Untouchable numbers (the 150232 terms up to 10^6).
H. J. J. te Riele, A theoretical and computational study of generalized aliquot sequences, Mathematisch Centrum, Amsterdam, 1976. See chapter 9.
Eric Weisstein's World of Mathematics, Untouchable Number.
Wikipedia, Untouchable number.
Robert G. Wilson v, Letter to N. J. A. Sloane, Jul. 1992.

Cf. A001065, A048138, A057709, A064000, A078923, A152454, A231964, A283152, A284147.

untouchableQ[n_] := Catch[ Do[ If[n == DivisorSigma[1, k]-k, Throw[True]], {k, 0, (n-1)^2}]] === Null; Reap[ Table[ If[ untouchableQ[n], Print[n]; Sow[n]], {n, 2, 700}]][[2, 1]] (* Jean-François Alcover, Jun 29 2012, after Benoit Cloitre *)

isA078923(n)=if(n==0 || n==1, return(1)); for(m=1,(n-1)^2, if( sigma(m)-m == n, return(1))); 0
isA005114(n)=!isA078923(n)
for(n=1,700, if (isA005114(n), print(n))) \\ R. J. Mathar, Aug 10 2006

is(n)=if(n%2 && n<4e18, return(n==5)); forfactored(m=1,(n-1)^2, if(sigma(m)-m[1]==n, return(0))); 1 \\ Charles R Greathouse IV, Dec 05 2022

from sympy import divisor_sigma as sigma
from functools import cache
@cache
def f(m): return sigma(m)-m
def okA005114(n):
    if n < 2: return 0
    return not any(f(m) == n for m in range(1, (n-1)**2+1))
print([k for k in range(289) if okA005114(k)]) # Michael S. Branicky, Nov 16 2024

# faster for intial segment of sequence
from itertools import count, islice
from sympy import divisor_sigma as sigma
def agen(): # generator of terms
    n, touchable, t = 2, {0, 1}, 1
    for m in count(2):
        touchable.add(sigma(m)-m)
        while m > t:
            if n not in touchable:
                yield n
            else:
                touchable.discard(n)
            n += 1
            t = (n-1)**2
print(list(islice(agen(), 20))) # Michael S. Branicky, Nov 16 2024

More terms from David W. Wilson

A001274 Numbers k such that phi(k) = phi(k+1).

Original entry on oeis.org

1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545, 32864, 38804, 39524, 46215, 48704, 49215, 49335, 56864, 57584, 57645, 64004, 65535, 73124, 105524, 107864, 123824, 131144, 164175, 184635

Offset: 1

N. J. A. Sloane

Unlike totients, cototient(x + 1) = cototient(x) never holds (except 2 - phi(2) = 3 - phi(3) = 1) because cototient(x) is congruent to x modulo 2. - Labos Elemer, Aug 08 2001
Lal-Gillard and Firoozbakht ask whether there is another pair of consecutive integers in this sequence, apart from a(16) + 1 = a(17) = 5187, see link. - M. F. Hasler, Jan 05 2011
There are 5236 terms less than 10^12. - Jud McCranie, Feb 13 2012
Up to 10^13 there are 10755 terms, and no further consecutive pairs like (5186, 5187). - Giovanni Resta, Feb 27 2014
A051179(k) for k from 0 to 5 are in the sequence. No other members of A051179 are in the sequence, because phi(2^(2^k)-1) = Product_{j=1..k-1} phi(2^(2^j)+1) and phi(2^(2^5)+1) < 2^(2^5) so if k > 5, phi(2^(2^k)-1) < Product_{j=1..k-1} 2^(2^j) = 2^(2^k-1) = phi(2^(2^k)). - Robert Israel, Mar 31 2015
Number of terms < 10^k, k=1,2,3,...: 2, 3, 10, 17, 36, 68, 142, 306, 651, 1267, 2567, 5236, 10755, ..., . - Robert G. Wilson v, Apr 10 2019
Conjecture: Except for the first two terms, all terms are composite and congruent to either 2 or 3 (mod 6). - Robert G. Wilson v, Apr 10 2019
Paul Kinlaw has noticed that up to 10^13 the only counterexample to the above conjecture is a(7424) = 3044760173455. - Giovanni Resta, May 23 2019

			phi(3) = phi(4) = 2, so 3 is in the sequence.
phi(15) = phi(16) = 8, so 15 is in the sequence.

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 15, pp 5, Ellipses, Paris 2008.
R. K. Guy, Unsolved Problems Number Theory, Sect. B36.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Giovanni Resta, Table of n, a(n) for n = 1..10755 (terms < 10^13, a(1)-a(2567) from T. D. Noe, a(2568)-a(5236) from J. McCranie)
R. Baillie, Table of phi(n) = phi(n+1), Math. Comp., 30 (1976), 189-190.
Jonathan Bayless and Paul Kinlaw, Consecutive coincidences of Euler's function, International Journal of Number Theory, Vol. 12, No. 4 (2016), pp. 1011-1026.
Farideh Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 66.
Paul Kinlaw, Mitsuo Kobayashi and Carl Pomerance, On the equation phi(n) = phi(n+1), Acta Arithmetica, Vol. 196 (2020), pp. 69-92, alternative link.
V. L. Klee, Jr., Some remarks on Euler's totient function, Amer. Math. Monthly, 54 (1947), 332.
M. Lal and P. Gillard, On the equation phi(n) = phi(n+k), Math. Comp., 26 (1972), 579-583.
K. Miller, Solutions of phi(n) = phi(n+1) for 1 <= n <= 500000. Unpublished, 1972. [ Cf. (Untitled), Math. Comp., Vol. 27, p. 447, 1973 ].
Leo Moser, Some equations involving Euler's totient function, Amer. Math. Monthly, 56 (1949), 22-23.
J. Shallit, Letter to N. J. A. Sloane, Jul 17 1975.

Cf. A000010, A001494, A051953, A003276, A003275, A007015, A179186, A179187, A179188, A179189, A179202, A217139.

import Data.List (elemIndices)
a001274 n = a001274_list !! (n-1)
a001274_list = map (+ 1) $ elemIndices 0 $
                           zipWith (-) (tail a000010_list) a000010_list
-- Reinhard Zumkeller, May 20 2014, Mar 31 2011

[n: n in [1..3*10^5] | EulerPhi(n) eq EulerPhi(n+1)]; // Vincenzo Librandi, Apr 14 2015

select(n -> numtheory:-phi(n) = numtheory:-phi(n+1), [$1..10^5]); # Robert Israel, Mar 31 2015

Reap[For[n = 1; k = 2; f1 = 1, k <= 10^9, k++, f2 = EulerPhi[k]; If[f1 == f2, Print["a(", n, ") = ", k - 1]; Sow[k - 1]; n++]; f1 = f2]][[2, 1]] (* Jean-François Alcover, Mar 29 2011, revised Dec 26 2013 *)
Flatten[Position[Partition[EulerPhi[Range[200000]],2,1],{x_,x_}]] (* Harvey P. Dale, Dec 27 2015 *)
Select[Range[1000], EulerPhi[#] == EulerPhi[# + 1] &] (* Alonso del Arte, Oct 03 2014 *)
SequencePosition[EulerPhi[Range[200000]],{x_,x_}][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, May 01 2018 *)
k = 8; lst = {1, 3}; While[k < 200000, If[ !PrimeQ[k +1], ep = EulerPhi[k +1]; If[ EulerPhi[k] == ep, AppendTo[lst, k]]; If[ep == EulerPhi[k +2], AppendTo[lst, k +1]]]; k += 6]; lst (* Robert G. Wilson v, Apr 10 2019 *)

is(n)=eulerphi(n)==eulerphi(n+1) \\ Charles R Greathouse IV, Feb 27 2014

list(lim)=my(v=List(),old=1); forfactored(n=2,lim\1+1, my(new=eulerphi(n)); if(old==new, listput(v,n[1]-1)); old=new); Vec(v) \\ Charles R Greathouse IV, Jul 17 2022

Conjecture: a(n) ~ C*n^3*log(n), where C = 9/Pi^2 = 0.91189... - Thomas Ordowski, Oct 21 2014

Sum_{n>=1} 1/a(n) is in the interval (1.4324884, 7.8358) (Kinlaw et al., 2020; an upper bound 441702 was given by Bayless and Kinlaw, 2016). - Amiram Eldar, Oct 15 2020

More terms from David W. Wilson

A007369 Numbers n such that sigma(x) = n has no solution.

Original entry on oeis.org

2, 5, 9, 10, 11, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 33, 34, 35, 37, 41, 43, 45, 46, 47, 49, 50, 51, 52, 53, 55, 58, 59, 61, 64, 65, 66, 67, 69, 70, 71, 73, 75, 76, 77, 79, 81, 82, 83, 85, 86, 87, 88, 89, 92, 94, 95, 97, 99, 100, 101, 103, 105, 106, 107, 109, 111, 113

Offset: 1

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

nonn

With an initial 1, may be constructed inductively in stages from the list L = {1,2,3,....} by the following sieve procedure. Stage 1. Add 1 as the first term of the sequence a(n) and strike off 1 from L. Stage n+1. Add the first (i.e. leftmost) term k of L as a new term of the sequence a(n) and strike off k, sigma(k), sigma(sigma(k)),.... from L. - Joseph L. Pe, May 08 2002
This sieve is a special case of a more general sieve. Let D be a subset of N and let f be an injection on D satisfying f(n) > n. Define the sieve process as follows: 1. Start with the empty sequence S and let E = D. 2. Append the smallest element s of E to S. 3. Remove s, f(s), f(f(s)), f(f(f(s))), ... from E. 4. Go to step 2. After this sieving process, S = D - f(D). To get the current sequence, take f = sigma and D = {n | n >= 2}. - Max Alekseyev, Aug 08 2005
By analogy with the untouchable numbers (A005114), these numbers could be named "sigma-untouchable". - Daniel Lignon, Mar 28 2014
The asymptotic density of this sequence is 1 (Niven, 1951, Rao and Murty, 1979). - Amiram Eldar, Jul 23 2020

			a(4) = 10 because there is no x < 10 whose sigma(x) = 10.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. F. Hasler, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Ivan Niven, The asymptotic density of sequences, Bull. Amer. Math. Soc., Vol. 57 (1951), pp. 420-434.
R. Sita Rama Chandra Rao and G. Sri Rama Chandra Murty, On a theorem of Niven, Canadian Mathematical Bulletin, Vol 22, No. 1 (1979), pp. 113-115.
R. G. Wilson, V, Letter to N. J. A. Sloane, Jul. 1992

Complement of A002191.
See A083532 for the gaps, i.e., first differences.
See A048995 for the missed sums of nontrivial divisors.

a = {}; Do[s = DivisorSigma[1, n]; a = Append[a, s], {n, 1, 115} ]; Complement[ Table[ n, {n, 1, 115} ], Union[a] ]

list(lim)=my(v=List(),u=vectorsmall(lim\1),t); for(n=1,lim, t=sigma(n); if(t<=lim, u[t]=1)); for(n=2,lim, if(u[n]==0, listput(v,n))); Vec(v) \\ Charles R Greathouse IV, Mar 09 2017

A007369_list(LIM,m=0,L=List(),s)={for(n=2,LIM,(s=sigma(n-1))>LIM || bittest(m,s) || m+=1<M. F. Hasler, Mar 12 2018

A175192(a(n)) = 0, A054973(a(n)) = 0. - Jaroslav Krizek, Mar 01 2010

a(n) < 2n + sqrt(8n). - Charles R Greathouse IV, Oct 23 2015

More terms from David W. Wilson

A007368 Smallest k such that sigma(x) = k has exactly n solutions.

Original entry on oeis.org

2, 1, 12, 24, 96, 72, 168, 240, 336, 360, 504, 576, 1512, 1080, 1008, 720, 2304, 3600, 5376, 2520, 2160, 1440, 10416, 13392, 3360, 4032, 3024, 7056, 6720, 2880, 6480, 10800, 13104, 5040, 6048, 4320, 13440, 5760, 18720, 20736, 19152, 22680, 43680

Offset: 0

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

nonn

It's not obvious that a(n) exists for all n; I'd like to see a proof. - David Wasserman, Jun 07 2002
Note that k-1 is frequently prime. See A115374 for the least prime. For each n, it appears that there are an infinite number of k such that sigma(x)=k has exactly n solutions. - T. D. Noe, Jan 21 2006
According to Sierpiński, H. J. Kanold proved that there is a k such that sigma(x)=k has n or more solutions. Sierpiński states that Erdős proved that if, for some k, sigma(x)=k has exactly n solutions, then there are an infinite number of such k. - T. D. Noe, Oct 18 2006
Index of the first occurrence of n in A054973. - Jaroslav Krizek, Apr 25 2009

			a(10) = 504; {204, 220, 224, 246, 284, 286, 334, 415, 451, 503} is the set of x such that sigma(x) = 504.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe and Donovan Johnson, Table of n, a(n) for n = 0..5000 (terms up to a(429) from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Kevin Ford, Sergei Konyagin, On two conjectures of Sierpiński concerning the arithmetic functions σ and ϕ, arXiv:1910.08452 [math.NT], 2019.
W. Sierpiński, Elementary Theory of Numbers, Warszawa 1964, page 166.
R. G. Wilson, V, Letter to N. J. A. Sloane, Jul. 1992

Cf. A000203, A054973, A002191, A007609.
Cf. A115374 (least prime p such that sigma(x)=sigma(p) has exactly n solutions).
Cf. A007369, A007370, A007371, A007372 (n such that sigma(x)=k has 0, 1, 2 and 3 solutions).
Cf. A184393, A184394, A201915 (smallest solution, largest solution, triangle of solutions for sigma(x)=a(n)).

Needs["Statistics`DataManipulation`"]; s=DivisorSigma[1, Range[10^5]]; f=Frequencies[s]; fs=Sort[f]; tfs=Transpose[fs][[1]]; utfs=Union[tfs]; firstMissing=First[Complement[Range[Last[utfs]], utfs]]; pos=1; Table[While[tfs[[pos]]T. D. Noe *)
terms = 100; cnt = DivisorSigma[1, Range[terms^3]] // Tally // Sort; a[0] = 2; a[n_] := SelectFirst[cnt, #[[2]] == n&][[1]]; Table[a[n], {n, 0, terms - 1}] (* Jean-François Alcover, Jul 18 2017 *)

More terms from David W. Wilson

A007370 Numbers k such that sigma(x) = k has a unique solution.

Original entry on oeis.org

1, 3, 4, 6, 7, 8, 13, 14, 15, 20, 28, 30, 36, 38, 39, 40, 44, 57, 62, 63, 68, 74, 78, 91, 93, 102, 110, 112, 121, 127, 133, 138, 150, 158, 160, 162, 164, 171, 174, 176, 183, 194, 195, 198, 200, 204, 212, 217, 222, 230, 242, 255, 256, 258, 260, 266, 278, 282

Offset: 1

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

nonn

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
Wacław Sierpiński, Elementary Theory of Numbers, Państ. Wydaw. Nauk., Warsaw, 1964, p. 165.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Wacław Sierpiński, Elementary Theory of Numbers, Warszawa, 1964.
Robert G. Wilson v, Letter to N. J. A. Sloane, Jul. 1992.

Cf. A000203.

Number of solutions: A007369 (0), this sequence (1), A007371 (2), A007372 (3), A060660 (4), A060661 (5), A060662 (6), A060663 (7), A060664 (8), A060665 (9), A060666 (10), A060678 (11), A060676 (12).

a = Table[ 0, {250} ]; Do[ s = DivisorSigma[ 1, n ]; If[ s < 251, a[ [ s ] ]++ ], {n, 1, 250} ]; Select[ Range[ 250 ], a[ [ # ] ] == 1 & ]

list(lim)=my(v=vectorsmall(lim\1), u=List(), s); for(k=1,#v,s=sigma(k); if(s<=#v, v[s]++)); for(k=1,#v,if(v[k]==1, listput(u,k))); Vec(u) \\ Charles R Greathouse IV, Jun 15 2015

is(k) = invsigmaNum(k) == 1 \\ Amiram Eldar, Nov 18 2024, using Max Alekseyev's invphi.gp

A007373 Numbers k such that sigma(k+2) = sigma(k).

Original entry on oeis.org

33, 54, 284, 366, 834, 848, 918, 1240, 1504, 2910, 2913, 3304, 4148, 4187, 6110, 6902, 7169, 7912, 9359, 10250, 10540, 12565, 15085, 17272, 17814, 19004, 19688, 21410, 21461, 24881, 25019, 26609, 28124, 30592, 30788, 31484, 38210, 38982, 39786, 40310, 45354

Offset: 1

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v

nonn

Numbers k such that antisigma(k+2) - antisigma(k) = 2*k + 3, where antisigma(m) = A024816(m) = sum of nondivisors of m. - Jaroslav Krizek, Mar 17 2013

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 33, pp 12, Ellipses, Paris 2008.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Donovan Johnson, Table of n, a(n) for n = 1..10000 (first 1000 terms from Zak Seidov)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
A. Weingartner, On the Solutions of sigma(n) = sigma(n+k), Journal of Integer Sequences, Vol. 14 (2011), #11.5.5.
R. G. Wilson, V, Letter to N. J. A. Sloane, Jul. 1992

Essentially the same as A055574.

Cf. A002961, A015861, A015863, A015865, A015866, A015867, A015876, A015877, A015880, A015881, A015882, A015883, A181647. [From Reinhard Zumkeller, Nov 03 2010]

Flatten[Position[Partition[DivisorSigma[1,Range[300000]],3,1], {x_, , x}]] (* Harvey P. Dale, Aug 08 2011 *)
SequencePosition[DivisorSigma[1,Range[300000]],{x_,,x}][[All,1]] (* Harvey P. Dale, Nov 17 2022 *)

je=[]; for(n=1,10^5,a=sigma(n); b=sigma(n+2); if(a==b,je=concat(je,n))); je

More terms from Jason Earls, Jul 20 2001

cp's OEIS Frontend

A342702 Indices of records of A007015.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A015887 Erroneous version of A007015.

Views

Author

Keywords

A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A005277 Nontotients: even numbers k such that phi(m) = k has no solution.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A005114 Untouchable numbers, also called nonaliquot numbers: impossible values for the sum of aliquot parts function (A001065).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Python

Extensions

A001274 Numbers k such that phi(k) = phi(k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI