A007621 -id:A007621 - cp's OEIS frontend

A005153 Practical numbers: positive integers m such that every k <= sigma(m) is a sum of distinct divisors of m. Also called panarithmic numbers.

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 228, 234, 240, 252

Offset: 1

N. J. A. Sloane

Equivalently, positive integers m such that every number k <= m is a sum of distinct divisors of m.
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
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
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
Conjecture: The sequence a(n)^(1/n) (n=3,4,...) is strictly decreasing to the limit 1. - Zhi-Wei Sun, Jan 12 2013
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
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
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
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
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
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
Erdős (1950) and Erdős and Loxton (1979) proved that the asymptotic density of practical numbers is 0. - Amiram Eldar, Feb 13 2021
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
From Hal M. Switkay, Dec 22 2022: (Start)
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).
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)
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

H. Heller, Mathematical Buds, Vol. 1, Chap. 2, pp. 10-22, Mu Alpha Theta OK, 1978.
Malcolm R. Heyworth, More on Panarithmic Numbers, New Zealand Math. Mag., Vol. 17 (1980), pp. 28-34 [ ISSN 0549-0510 ].
Ross Honsberger, Mathematical Gems, M.A.A., 1973, p. 113.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 146-147.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Thomas Bloom, Problem 18, Erdős Problems.
Wayne Dymacek, Letter to N. J. A. Sloane, Jun 15 1978.
David Eppstein, Egyptian fractions with practical denominators, Nov 20, 2016
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Paul Erdős, On a Diophantine equation (in Hungarian, with Russian and English summaries), Mat. Lapok, Vol. 1 (1950), pp. 192-210.
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.
James Grimes and Brady Haran, Practical Numbers, Numberphile video (2023).
Harvey J. Hindin, Quasipractical numbers, IEEE Communications Magazine, Vol. 18, No. 2 (March 1980), pp. 41-45.
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.
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.
Maurice Margenstern, Les nombres pratiques: théorie, observations et conjectures, Journal of Number Theory, Volume 37, Issue 1 (January 1991), pp. 1-36.
C. McLeman, Practical number, PlanetMath.org.
Giuseppe Melfi, On two conjectures about practical numbers, J. Number Theory, Vol. 56, No. 1 (1996), pp. 205-210 [MR96i:11106].
Giuseppe Melfi, On certain positive integer sequences, arXiv:0404555 [math.NT], 2004.
Giuseppe Melfi, A survey on practical numbers, Rend. Sem. Mat. Univ. Politec. Torino, Vol. 53, No. 4 (1995), pp. 347-359.
Giuseppe Melfi, Practical Numbers (old link).
Paul Pollack and Lola Thompson, Practical pretenders, arXiv:1201.3168 [math.NT], Jan 16 2012.
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.
Carl Pomerance and Andreas Weingartner, On primes and practical numbers, Ramanujan J. (2021); arXiv preprint, arXiv:2007.11062 [math.NT], 2020.
Eric Saias, Entiers à diviseurs denses 1, J. Number Theory, Vol. 62, No. 1 (1997), pp. 163-191; uses this definition.
Carlo Sanna, Practical central binomial coefficients, arXiv:2004.05376 [math.NT], 2020.
Sai Teja Somu, Ting Hon Stanford Li, and Andrzej Kukla, On Some Results on Practical Numbers, INTEGERS, Volume 23, A68, 2023 [MR4643065].
Sai Teja Somu and Duc Van Khanh Tran, On Sums of Practical Numbers and Polygonal Numbers, arXiv:2403.13533 [math.NT], 2024.
A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180.
B. M. Stewart, Sums of distinct divisors, Amer. J. Math., Vol. 76, No. 4 (1954), pp. 779-785 [MR64800]
Zhi-Wei Sun, A conjecture on unit fractions involving primes, preprint, 2015.
Terence Tao, Erdős problem database, see entry no. 18.
Peter Taylor, Table of n, a(n) for n = 1..1000000.
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.
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.
Andreas Weingartner, Uniform distribution of alpha*n modulo one for a family of integer sequences, arXiv:2303.16819 [math.NT], 2023.
Eric Weisstein's World of Mathematics, Practical Number.
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]
Wikipedia, Practical number.
Robert G. Wilson v, Letter to N. J. A. Sloane, date unknown.

Subsequence of A103288.
Cf. A002093, A007620 (second definition), A030057, A033630, A119348, A174533, A174973.
Cf. A027750.

a005153 n = a005153_list !! (n-1)
a005153_list = filter (\x -> all (p $ a027750_row x) [1..x]) [1..]
   where p _  0 = True
         p [] _ = False
         p ds'@(d:ds) m = d <= m && (p ds (m - d) || p ds m)
-- Reinhard Zumkeller, Feb 23 2014, Oct 27 2011

isA005153 := proc(n)
    local ifs,pprod,p,i ;
    if n = 1 then
        return true;
    elif type(n,'odd') then
        return false ;
    end if;
    # not using ifactors here directly because no guarantee primes are sorted...
    ifs := ifactors(n)[2] ;
    pprod := 1;
    for p in sort(numtheory[factorset](n) ) do
        for i in ifs do
            if op(1,i) = p then
                if p > 2 and p > 1+numtheory[sigma](pprod) then
                    return false ;
                end if;
                pprod := pprod*p^op(2,i) ;
            end if;
        end do:
    end do:
    return true ;
end proc:
for n from 1 to 300 do
    if isA005153(n)  then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Jul 07 2023

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 *)

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

from sympy import factorint
def is_A005153(n):
    if n & 1: return n == 1
    f = factorint(n) ; P = (2 << f.pop(2)) - 1
    for p in f: # factorint must have prime factors in increasing order
        if p > 1 + P: return
        P *= p**(f[p]+1)//(p-1)
    return True # M. F. Hasler, Jan 02 2023

from sympy import divisors;from more_itertools import powerset
[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

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

More precisely, a(n) = k*n*log(n*log(n)) + O(n), where k = 0.74846... (see comments). - Andreas Weingartner, Jun 26 2021

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 09 2004
Erroneous comment removed by T. D. Noe, Nov 14 2010
Definition changed to exclude n = 0 explicitly by M. F. Hasler, Jan 19 2013

A007620 Numbers m such that every k <= m is a sum of proper divisors of m (for m>1).

Original entry on oeis.org

1, 6, 12, 18, 20, 24, 28, 30, 36, 40, 42, 48, 54, 56, 60, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 228, 234, 240, 252, 260, 264, 270, 272, 276, 280, 288, 294, 300, 304, 306

Offset: 1

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

This sequence was formerly called "practical numbers (second definition)" because it was thought this was the definition used in Srinivasan's original paper. However, in Srinivasan's paper, one can read that his definition is "k < m". Stewart proves that Srinivasan's definition is equivalent to requiring every k <= sigma(m) be the sum of distinct divisors of m. This sequence is a subsequence of the practical numbers, A005153. - T. D. Noe, Apr 02 2010

A005153 without terms larger than 1 that are almost-perfect numbers (numbers k such that sigma(k) = 2*k-1, the only known such numbers are the powers of 2, A000079). - Amiram Eldar, Apr 07 2023

Ross Honsberger, Mathematical Gems, M.A.A., 1973, p. 113.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..1000
A. K. Srinivasan, Practical numbers, Current Science, 17 (1948), 179-180.
B. M. Stewart, Sums of distinct divisors, American Journal of Mathematics, Vol. 76, No. 4 (1954), pp. 779-785.
Robert G. Wilson v, Letter to N. J. A. Sloane, date unknown.

Cf. A005153 (first definition).

Cf. A000079, A027751.

a007620 n = a007620_list !! (n-1)
a007620_list = 1 : filter (\x -> all (p $ a027751_row x) [1..x]) [2..]
   where p _  0 = True
         p [] _ = False
         p ds'@(d:ds) m = d <= m && (p ds (m - d) || p ds m)
-- Reinhard Zumkeller, Feb 23 2014

DeleteCases[ A005835, q_/; (Count[ CoefficientList[ Series[ Times@@( (1+z^#)& /@ Divisors[ q ] ), {z, 0, q} ], z ], 0 ]>0) ] (* Wouter Meeussen *)

from itertools import count, islice
from sympy import divisors
def A007620_gen(startvalue=1): # generator of terms >= startvalue
    for m in count(max(startvalue,1)):
        if m == 1:
            yield 1
        else:
            c = {0}
            for d in divisors(m,generator=True):
                if d < m:
                    c |= {a+d for a in c}
            if all(a in c for a in range(m+1)):
                yield m
A007620_list = list(islice(A007620_gen(),30)) # Chai Wah Wu, Jul 06 2023

cp's OEIS Frontend

A005153 Practical numbers: positive integers m such that every k <= sigma(m) is a sum of distinct divisors of m. Also called panarithmic numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A007620 Numbers m such that every k <= m is a sum of proper divisors of m (for m>1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

A353061 Zumkeller numbers (A083207) that are not practical numbers (A005153).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A035480 Pseudoperfect numbers (A005835) that are not practical (second definition, A007620).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions