A003624 Duffinian numbers: composite numbers k relatively prime to sigma(k).

4, 8, 9, 16, 21, 25, 27, 32, 35, 36, 39, 49, 50, 55, 57, 63, 64, 65, 75, 77, 81, 85, 93, 98, 100, 111, 115, 119, 121, 125, 128, 129, 133, 143, 144, 155, 161, 169, 171, 175, 183, 185, 187, 189, 201, 203, 205, 209, 215, 217, 219, 221, 225, 235, 237, 242, 243, 245, 247

Offset: 1

Author

N. J. A. Sloane, Mira Bernstein, Sep 19 1994

Keywords

• nonn

Comments

All prime powers greater than 1 are in the sequence. No factorial number can be a term. - Arkadiusz Wesolowski, Feb 16 2014

Even terms are in A088827. Any term also in A005153 is either an even square or twice an even square not divisible by 3. - Jaycob Coleman, Jun 08 2014

All primes satisfy the second condition since gcd(p, p+1) = 1, thus making this sequence a proper subset of A014567. - Robert G. Wilson v, Oct 02 2014

Examples

			4 is in the sequence since it is not a prime, its divisors 1, 2, and 4 sum to 7, and gcd(7, 4) = 1.
21 is in the sequences since it is not a prime, and its divisors 1, 3, 7, and 21 sum to 32, which is coprime to 21.
		

References

• T. Koshy, Elementary number theory with applications, Academic Press, 2002, p. 141, exerc. 6,7,8 and 9.
• L. Richard Duffy, The Duffinian numbers, Journal of Recreational Mathematics 12 (1979), pp. 112-115.
• Peter Heichelheim, There exist five Duffinian consecutive integers but not six, Journal of Recreational Mathematics 14 (1981-1982), pp. 25-28.
• J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 64.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Florian Luca, On the densities of some subsets of integers, Missouri Journal of Mathematical Sciences 19:3 (2007), pp. 167-170.
• Rose Mary Zbiek, What can we say about the Duffinian numbers?, The Pentagon 42:2 (1983), pp. 99-109.

Crossrefs

Cf. A000203, A002808, A014567, A025475.

Programs

Haskell

a003624 n = a003624_list !! (n-1)
a003624_list = filter ((== 1) . a009194) a002808_list
-- Reinhard Zumkeller, Mar 23 2013

Mathematica

fQ[n_] := n != 1 && !PrimeQ[n] && GCD[n, DivisorSigma[1, n]] == 1; Select[ Range@ 280, fQ]

PARI

is(n)=gcd(n,sigma(n))==1&&!isprime(n) \\ Charles R Greathouse IV, Feb 13 2013

Python

from math import gcd
from itertools import count, islice
from sympy import isprime, divisor_sigma
def A003624_gen(startvalue=2): # generator of terms
    return filter(lambda k:not isprime(k) and gcd(k,divisor_sigma(k))==1,count(max(startvalue,2)))
A003624_list = list(islice(A003624_gen(),30)) # Chai Wah Wu, Jul 06 2023

Formula

A009194(a(n)) * (1 - A010051(a(n))) = 1. - Reinhard Zumkeller, Mar 23 2013

a(n) >> n log log log n, see Luca. (Clearly excluding the primes only makes the n-th term larger.) - Charles R Greathouse IV, Feb 17 2014