A019294 Number (> 0) of iterations of sigma (A000203) required to reach a multiple of n when starting with n.
1, 2, 4, 2, 5, 1, 5, 2, 7, 4, 15, 3, 13, 3, 2, 2, 13, 4, 12, 5, 2, 13, 16, 2, 17, 4, 9, 1, 78, 7, 10, 4, 17, 11, 6, 5, 28, 22, 4, 7, 39, 2, 16, 16, 16, 10, 32, 5, 13, 17, 9, 3, 58, 11, 19, 5, 13, 67, 97, 2, 23, 5, 16, 2, 4, 8, 101, 21, 19, 11, 50, 4, 20, 20, 23, 14, 21, 10, 36, 5, 15
Offset: 1
Examples
If n = 9 the iteration sequence is s(9) = {9, 13, 14, 24, 60, 168, 480, 1512, 4800, 15748, 28672} and Mod[s(9), 9] = {0, 4, 5, 6, 6, 6, 3, 0, 3, 7, 7}. The first iterate which is a multiple of 9 is the 7th = 1512, so a(9) = 7. For n = 67, the 101st iterate is the first, so a(67) = 101. Usually several iterates are divisible by the initial value. E.g., if n = 6, then 91 of the first 100 iterates are divisible by 6.
A difficult term to compute: a(461) = 557. - _Don Reble_, Jun 23 2005
References
- Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.
Links
- Don Reble, Table of n, a(n) for n = 1..1578 (Terms a(1..400) from T. D. Noe, Nov 2007; a(401..659) from Michel Marcus, Jan 02 2017), Feb 20 2022.
- G. L. Cohen and H. J. J. te Riele, Iterating the sum-of-divisors function, Experimental Mathematics, 5 (1996), pp. 93-100. See Table 2, p. 95.
- Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
- Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
- Carl Pomerance, On the composition of the functions sigma and phi, Colloq. Math., 59 (1989), 11-15.
- Wikipedia, Iterated function, as of Jan 02 2020.
- Zeraoulia Rafik, On congruence of the iterated form sigma^k(m) = 0 mod m, arXiv:2102.09941 [math.NT], 2021.
Crossrefs
Programs
-
Haskell
a019294 n = snd $ until ((== 0) . (`mod` n) . fst) (\(x, i) -> (a000203 x, i + 1)) (a000203 n, 1) -- Reinhard Zumkeller, Aug 02 2012 -
Magma
a:=[]; f:=func
-
Maple
A019294 := proc(n) local a,nitr ; a := 1 ; nitr := numtheory[sigma](n); while modp(nitr,n) <> 0 do nitr := numtheory[sigma](nitr) ; a := a+1 ; end do: return a; end proc: # R. J. Mathar, Aug 22 2016
-
Mathematica
f[n_, m_] := Block[{d = DivisorSigma[1, n]}, If[ Mod[d, m] == 0, 0, d]]; Table[ Length[ NestWhileList[ f[ #, n] &, n, # != 0 &]] - 1, {n, 84}] (* Robert G. Wilson v, Jun 24 2005 *) Table[Length[NestWhileList[DivisorSigma[1,#]&,DivisorSigma[1,n], !Divisible[ #,n]&]],{n,90}] (* Harvey P. Dale, Mar 04 2015 *) -
PARI
a(n)=if(n<0,0,c=1; s=n; while(sigma(s)%n>0,s=sigma(s); c++); c)
-
PARI
apply( A019294(n,s=n)=for(k=1,oo,(s=sigma(s))%n||return(k)), [1..99]) \\ M. F. Hasler, Jan 07 2020
Formula
Conjecture: lim_{n -> oo} log(Sum_{k=1..n} a(k))/log(n) = C = 1.6... - Benoit Cloitre, Aug 24 2002
From Michel Marcus, Jan 02 2017: (Start)
a(n) = 1 for n in A007691.
Extensions
Additional comments from Labos Elemer, Jun 20 2001
Edited by M. F. Hasler, Jan 07 2020
Comments