# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a005153 Showing 1-1 of 1 %I A005153 M0991 #279 Feb 16 2025 08:32:28 %S A005153 1,2,4,6,8,12,16,18,20,24,28,30,32,36,40,42,48,54,56,60,64,66,72,78, %T A005153 80,84,88,90,96,100,104,108,112,120,126,128,132,140,144,150,156,160, %U A005153 162,168,176,180,192,196,198,200,204,208,210,216,220,224,228,234,240,252 %N A005153 Practical numbers: positive integers m such that every k <= sigma(m) is a sum of distinct divisors of m. Also called panarithmic numbers. %C A005153 Equivalently, positive integers m such that every number k <= m is a sum of distinct divisors of m. %C A005153 2^r is a member for all r as every number < = sigma(2^r) = 2^(r+1)-1 is a sum of a distinct subset of divisors {1, 2, 2^2, ..., 2^m}. - _Amarnath Murthy_, Apr 23 2004 %C A005153 Also, numbers m such that A030057(m) > m. This is a consequence of the following theorem (due to Stewart), found at the McLeman link: An integer m >= 2 with factorization Product_{i=1..k} p_i^e_i with the p_i in ascending order is practical if and only if p_1 = 2 and, for 1 < i <= k, p_i <= sigma(Product_{j < i} p_j^e_j) + 1. - _Franklin T. Adams-Watters_, Nov 09 2006 %C A005153 Practical numbers first appear in Srinivasan's short paper, which contains terms up to 200. Let m be a practical number. He states that (1) if m>2, m is a multiple of 4 or 6; (2) sigma(m) >= 2*m-1 (A103288); and (3) 2^t*m is practical. He also states that highly composite numbers (A002182), perfect numbers (A000396), and primorial numbers (A002110) are practical. - _T. D. Noe_, Apr 02 2010 %C A005153 Conjecture: The sequence a(n)^(1/n) (n=3,4,...) is strictly decreasing to the limit 1. - _Zhi-Wei Sun_, Jan 12 2013 %C A005153 Conjecture: For any positive rational number r, there are finitely many pairwise distinct practical numbers q(1)..q(k) such that r = Sum_{j=1..k} 1/q(j). For example, 2 = 1/1 + 1/2 + 1/4 + 1/6 + 1/12 with 1, 2, 4, 6 and 12 all practical, and 10/11 = 1/2 + 1/4 + 1/8 + 1/48 + 1/132 + 1/176 with 2, 4, 8, 48, 132 and 176 all practical. - _Zhi-Wei Sun_, Sep 12 2015 %C A005153 Analogous with the {1 union primes} (A008578), practical numbers form a complete sequence. This is because it contains all powers of 2 as a subsequence. - _Frank M Jackson_, Jun 21 2016 %C A005153 Sun's 2015 conjecture on the existence of Egyptian fractions with practical denominators for any positive rational number is true. See the link "Egyptian fractions with practical denominators". - _David Eppstein_, Nov 20 2016 %C A005153 Conjecture: if all divisors of m are 1 = d_1 < d_2 < ... < d_k = m, then m is practical if and only if d_(i+1)/d_i <= 2 for 1 <= i <= k-1. - _Jianing Song_, Jul 18 2018 %C A005153 The above conjecture is incorrect. The smallest counterexample is 78 (for which one of these quotients is 13/6; see A174973). m is practical if and only if the divisors of m form a complete subsequence. See Wikipedia links. - _Frank M Jackson_, Jul 25 2018 %C A005153 Reply to the comment above: Yes, and now I can show the opposite: The largest value of d_(i+1)/d_i is not bounded for practical numbers. Note that sigma(n)/n is not bounded for primorials, and primorials are practical numbers. For any constant c >= 2, let k be a practical number such that sigma(k)/k > 2c. By Bertrand's postulate there exists some prime p such that c*k < p < 2c*k < sigma(k), so k*p is a practical number with consecutive divisors k and p where p/k > c. For example, for k = 78 we have 13/6 > 2, and for 97380 we have 541/180 > 3. - _Jianing Song_, Jan 05 2019 %C A005153 Erdős (1950) and Erdős and Loxton (1979) proved that the asymptotic density of practical numbers is 0. - _Amiram Eldar_, Feb 13 2021 %C A005153 Let P(x) denote the number of practical numbers up to x. P(x) has order of magnitude x/log(x) (see Saias 1997). Moreover, we have P(x) = c*x/log(x) + O(x/(log(x))^2), where c = 1.33607... (see Weingartner 2015, 2020 and Remark 1 of Pomerance & Weingartner 2021). As a result, a(n) = k*n*log(n*log(n)) + O(n), where k = 1/c = 0.74846... - _Andreas Weingartner_, Jun 26 2021 %C A005153 From _Hal M. Switkay_, Dec 22 2022: (Start) %C A005153 Every number of least prime signature (A025487) is practical, thereby including two classes of number mentioned in Noe's comment. This follows from Stewart's characterization of practical numbers, mentioned in Adams-Watters's comment, combined with Bertrand's postulate (there is a prime between every natural number and its double, inclusive). %C A005153 Also, the first condition in Stewart's characterization (p_1 = 2) is equivalent to the second condition with index i = 1, given that an empty product is equal to 1. (End) %C A005153 Conjecture: every odd number, beginning with 3, is the sum of a prime number and a practical number. Note that this conjecture occupies the space between the unproven Goldbach conjecture and the theorem that every even number, beginning with 2, is the sum of two practical numbers (Melfi's 1996 proof of Margenstern's conjecture). - _Hal M. Switkay_, Jan 28 2023 %D A005153 H. Heller, Mathematical Buds, Vol. 1, Chap. 2, pp. 10-22, Mu Alpha Theta OK, 1978. %D A005153 Malcolm R. Heyworth, More on Panarithmic Numbers, New Zealand Math. Mag., Vol. 17 (1980), pp. 28-34 [ ISSN 0549-0510 ]. %D A005153 Ross Honsberger, Mathematical Gems, M.A.A., 1973, p. 113. %D A005153 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %D A005153 A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180. %H A005153 Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe) %H A005153 Wayne Dymacek, Letter to N. J. A. Sloane, Jun 15 1978. %H A005153 David Eppstein, Egyptian fractions with practical denominators, Nov 20, 2016 %H A005153 David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018. %H A005153 Paul Erdős, On a Diophantine equation (in Hungarian, with Russian and English summaries), Mat. Lapok, Vol. 1 (1950), pp. 192-210. %H A005153 Paul Erdős and J. H. Loxton, Some problems in partitio numerorum, Journal of the Australian Mathematical Society, Vol. 27, No. 3 (1979), pp. 319-331. %H A005153 James Grimes and Brady Haran, Practical Numbers, Numberphile video (2023). %H A005153 Harvey J. Hindin, Quasipractical numbers, IEEE Communications Magazine, Vol. 18, No. 2 (March 1980), pp. 41-45. %H A005153 Paolo Leonetti and Carlo Sanna, Practical numbers among the binomial coefficients, Journal of Number Theory, Vol. 207 (2020), pp. 145-155; arXiv preprint, arXiv:1905.12023 [math.NT], 2019. %H A005153 Maurice Margenstern, Sur les nombres pratiques, (in French), Groupe d'étude en théorie analytique des nombres, 1 (1984-1985), Exposé No. 21, 13 p. %H A005153 Maurice Margenstern, Les nombres pratiques: théorie, observations et conjectures, Journal of Number Theory, Volume 37, Issue 1 (January 1991), pp. 1-36. %H A005153 C. McLeman, Practical number, PlanetMath.org. %H A005153 Giuseppe Melfi, On two conjectures about practical numbers, J. Number Theory, Vol. 56, No. 1 (1996), pp. 205-210 [MR96i:11106]. %H A005153 Giuseppe Melfi, On certain positive integer sequences, arXiv:0404555 [math.NT], 2004. %H A005153 Giuseppe Melfi, A survey on practical numbers, Rend. Sem. Mat. Univ. Politec. Torino, Vol. 53, No. 4 (1995), pp. 347-359. %H A005153 Giuseppe Melfi, Practical Numbers (old link). %H A005153 Paul Pollack and Lola Thompson, Practical pretenders, arXiv:1201.3168 [math.NT], Jan 16 2012. %H A005153 Carl Pomerance, Lola Thompson and Andreas Weingartner, On integers n for which X^n-1 has a divisor of every degree, arXiv:1511.03357 [math.NT], 2015. %H A005153 Carl Pomerance and Andreas Weingartner, On primes and practical numbers, Ramanujan J. (2021); arXiv preprint, arXiv:2007.11062 [math.NT], 2020. %H A005153 Eric Saias, Entiers à diviseurs denses 1, J. Number Theory, Vol. 62, No. 1 (1997), pp. 163-191; uses this definition. %H A005153 Carlo Sanna, Practical central binomial coefficients, arXiv:2004.05376 [math.NT], 2020. %H A005153 Sai Teja Somu, Ting Hon Stanford Li, and Andrzej Kukla, On Some Results on Practical Numbers, INTEGERS, Volume 23, A68, 2023 [MR4643065]. %H A005153 Sai Teja Somu and Duc Van Khanh Tran, On Sums of Practical Numbers and Polygonal Numbers, arXiv:2403.13533 [math.NT], 2024. %H A005153 A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180. %H A005153 B. M. Stewart, Sums of distinct divisors, Amer. J. Math., Vol. 76, No. 4 (1954), pp. 779-785 [MR64800] %H A005153 Zhi-Wei Sun, A conjecture on unit fractions involving primes, preprint, 2015. %H A005153 Peter Taylor, Table of n, a(n) for n = 1..1000000. %H A005153 Andreas Weingartner, Practical numbers and the distribution of divisors, The Quarterly Journal of Mathematics, Vol. 66, No. 2 (2015), pp. 743-758; arXiv preprint, arXiv:1405.2585 [math.NT], 2014-2015. %H A005153 Andreas Weingartner, The constant factor in the asymptotic for practical numbers, Int. J. Number Theory, 16 (2020), no. 3, 629-638; arXiv preprint, arXiv:1906.07819 [math.NT], 2019. %H A005153 Andreas Weingartner, Uniform distribution of alpha*n modulo one for a family of integer sequences, arXiv:2303.16819 [math.NT], 2023. %H A005153 Eric Weisstein's World of Mathematics, Practical Number. %H A005153 Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023] %H A005153 Wikipedia, Practical number. %H A005153 Robert G. Wilson v, Letter to N. J. A. Sloane, date unknown. %F A005153 Weingartner proves that a(n) ~ k*n log n, strengthening an earlier result of Saias. In particular, a(n) = k*n log n + O(n log log n). - _Charles R Greathouse IV_, May 10 2013 %F A005153 More precisely, a(n) = k*n*log(n*log(n)) + O(n), where k = 0.74846... (see comments). - _Andreas Weingartner_, Jun 26 2021 %p A005153 isA005153 := proc(n) %p A005153 local ifs,pprod,p,i ; %p A005153 if n = 1 then %p A005153 return true; %p A005153 elif type(n,'odd') then %p A005153 return false ; %p A005153 end if; %p A005153 # not using ifactors here directly because no guarantee primes are sorted... %p A005153 ifs := ifactors(n)[2] ; %p A005153 pprod := 1; %p A005153 for p in sort(numtheory[factorset](n) ) do %p A005153 for i in ifs do %p A005153 if op(1,i) = p then %p A005153 if p > 2 and p > 1+numtheory[sigma](pprod) then %p A005153 return false ; %p A005153 end if; %p A005153 pprod := pprod*p^op(2,i) ; %p A005153 end if; %p A005153 end do: %p A005153 end do: %p A005153 return true ; %p A005153 end proc: %p A005153 for n from 1 to 300 do %p A005153 if isA005153(n) then %p A005153 printf("%d,",n) ; %p A005153 end if; %p A005153 end do: # _R. J. Mathar_, Jul 07 2023 %t A005153 PracticalQ[n_] := Module[{f,p,e,prod=1,ok=True}, If[n<1 || (n>1 && OddQ[n]), False, If[n==1, True, f=FactorInteger[n]; {p,e} = Transpose[f]; Do[If[p[[i]] > 1+DivisorSigma[1,prod], ok=False; Break[]]; prod=prod*p[[i]]^e[[i]], {i,Length[p]}]; ok]]]; Select[Range[200], PracticalQ] (* _T. D. Noe_, Apr 02 2010 *) %o A005153 (Haskell) %o A005153 a005153 n = a005153_list !! (n-1) %o A005153 a005153_list = filter (\x -> all (p $ a027750_row x) [1..x]) [1..] %o A005153 where p _ 0 = True %o A005153 p [] _ = False %o A005153 p ds'@(d:ds) m = d <= m && (p ds (m - d) || p ds m) %o A005153 -- _Reinhard Zumkeller_, Feb 23 2014, Oct 27 2011 %o A005153 (PARI) is_A005153(n)=bittest(n,0) && return(n==1); my(P=1); n && !for(i=2,#n=factor(n)~,n[1,i]>1+(P*=sigma(n[1,i-1]^n[2,i-1])) && return) \\ _M. F. Hasler_, Jan 13 2013 %o A005153 (Python) %o A005153 from sympy import factorint %o A005153 def is_A005153(n): %o A005153 if n & 1: return n == 1 %o A005153 f = factorint(n) ; P = (2 << f.pop(2)) - 1 %o A005153 for p in f: # factorint must have prime factors in increasing order %o A005153 if p > 1 + P: return %o A005153 P *= p**(f[p]+1)//(p-1) %o A005153 return True # _M. F. Hasler_, Jan 02 2023 %o A005153 (Python) %o A005153 from sympy import divisors;from more_itertools import powerset %o A005153 [i for i in range(1,253) if (lambda x:len(set(map(sum,powerset(x))))>sum(x))(divisors(i))] # _Nicholas Stefan Georgescu_, May 20 2023 %Y A005153 Subsequence of A103288. %Y A005153 Cf. A002093, A007620 (second definition), A030057, A033630, A119348, A174533, A174973. %Y A005153 Cf. A027750. %K A005153 nonn,nice,easy %O A005153 1,2 %A A005153 _N. J. A. Sloane_ %E A005153 More terms from Pab Ter (pabrlos(AT)yahoo.com), May 09 2004 %E A005153 Erroneous comment removed by _T. D. Noe_, Nov 14 2010 %E A005153 Definition changed to exclude n = 0 explicitly by _M. F. Hasler_, Jan 19 2013 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE