A066272 Number of anti-divisors of n.

0, 0, 1, 1, 2, 1, 3, 2, 2, 3, 3, 2, 4, 3, 3, 2, 5, 4, 3, 3, 3, 5, 5, 2, 5, 3, 5, 5, 3, 3, 5, 6, 5, 3, 5, 2, 5, 7, 5, 4, 4, 5, 5, 3, 7, 5, 5, 3, 6, 6, 3, 7, 7, 3, 5, 3, 5, 7, 7, 6, 4, 5, 7, 2, 5, 5, 9, 7, 3, 5, 5, 6, 7, 5, 5, 5, 9, 5, 3, 5, 6, 7, 7, 4, 8, 5, 7, 7, 3, 5, 5, 5, 7, 9, 9, 1, 7, 8, 5, 4, 5, 7, 7, 7, 9

Offset: 1

Author

N. J. A. Sloane, Dec 31 2001

Keywords

• nonn
• easy

Comments

Anti-divisors are the numbers that do not divide a number by the largest possible margin. E.g. 20 has anti-divisors 3, 8 and 13. An alternative name for anti-divisor is unbiased non-divisors.

Definition: If an odd number i in the range 1 < i <= n divides N where N is any one of 2n-1, 2n or 2n+1 then d = N/i is called an anti-divisor of n. The numbers 1 and 2 have no anti-divisors.

Equivalently, an anti-divisor of n is a number d in the range [2,n-1] which does not divide n and is either a (necessarily odd) divisor of 2n-1 or 2n+1, or a (necessarily even) divisor of 2n.

Thus an anti-divisor of n is an integer d in [2,n-1] such that n == (d-1)/2, d/2, or (d+1)/2 (mod d), the class of d being -1, 0, or 1, respectively.

k is an anti-divisor of n if and only if 1 < k < n and | (n mod k) - k/2 | < 1. - Max Alekseyev, Jul 21 2007

The number of even anti-divisors of n is one less than the number of odd divisors of n; specifically, all but the largest odd divisor multiplied by the power of two dividing 2n (i.e., 2^A001511(n)). For example, the odd divisors of 18 are 1, 3, and 9, so the even anti-divisors of 18 are 1*4 = 4 and 3*4 = 12. - Franklin T. Adams-Watters, Sep 11 2009

2n-1 and 2n+1 are twin primes if and only if n has no odd anti-divisors (e.g., n=15 has no odd anti-divisors so 29 and 31 are twin primes). - Jon Perry, Sep 02 2012

Records are in A066464. - Robert G. Wilson v, Sep 03 2012

Examples

			For example, n = 18: 2n-1, 2n, 2n+1 are 35, 36, 37 with odd divisors > 1 {5,7,35}, {3,9}, {37} and quotients 7, 5, 1, 12, 4, 1, so the anti-divisors of 18 are 4, 5, 7, 12. Therefore a(18) = 4.
		

Links

• Diana Mecum and T. D. Noe, Table of n, a(n) for n = 1..10000
• Jon Perry, The Anti-divisor.
• Jon Perry, The Anti-divisor: Even More Anti-Divisors.

Crossrefs

Cf. A000005, A058838, A066464, A066241, A001227, A001511, A001620, A066417.

See A130799 for the anti-divisors.

Programs

Maple

antidivisors := proc(n)
    local a,k;
    a := {} ;
    for k from 2 to n-1 do
        if abs((n mod k)- k/2) < 1 then
            a := a union {k} ;
        end if;
     end do:
     a ;
end proc:
A066272 := proc(n)
    nops(antidivisors(n)) ;
end proc:
seq(A066272(n),n=1..120); # R. J. Mathar, May 24 2010

Mathematica

antid[ n_ ] := Select[ Union[ Join[ Select[ Divisors[ 2n - 1 ], OddQ[ # ] && # != 1 & ], Select[ Divisors[ 2n + 1 ], OddQ[ # ] && # != 1 & ], 2n / Select[ Divisors[ 2n ], OddQ[ # ] && # != 1 & ] ] ], # < n & ]; Table[ Length[ antid[ n ] ], {n, 1, 100} ]
f[n_] := Length@ Complement[ Sort@Join[ Select[ Union@ Flatten@ Divisors[{2 n - 1, 2 n + 1}], OddQ@ # && # < n &], Select[ Divisors[2 n], EvenQ@ # && # < n &]], Divisors@ n]; Array[f, 105] (* Robert G. Wilson v, Jul 17 2007 *)
nd[n_]:=Count[Range[2,n-1],?(Abs[Mod[n,#]-#/2]<1&)]; Array[nd,110] (* _Harvey P. Dale, Jul 11 2012 *)

PARI

al(n)=Vec(sum(k=1,n,(x^(3*k)+x*O(x^n))/(1-x^(2*k))+(x^(3*k+1)+x^(3*k+2)+x*O(x^n))/(1-x^(2*k+1)))) \\ Franklin T. Adams-Watters, Sep 11 2009

PARI

a(n) = if(n>1, numdiv(2*n+1) + numdiv(2*n-1) + numdiv(n/2^valuation(n,2)) - 5, 0) \\ Max Alekseyev, Apr 27 2010

PARI

antidivisors(n)=select(t->n%t && tCharles R Greathouse IV, May 12 2016

Python

from sympy import divisors
def A066272(n):
    return len([d for d in divisors(2*n) if n > d >=2 and n%d]) +  len([d for d in divisors(2*n-1) if n > d >=2 and n%d]) +  len([d for d in divisors(2*n+1) if n > d >=2 and n%d]) # Chai Wah Wu, Aug 11 2014

Formula

G.f.: Sum_{k>0} x^(3k) / (1 - x^(2k)) + (x^(3k+1) + x^(3k+2)) / (1 - x^(2k+1)). - Franklin T. Adams-Watters, Sep 11 2009

a(n) = A000005(2*n-1) + A000005(2*n+1) + A001227(n) - 5. - Max Alekseyev, Apr 27 2010

a(n) = Sum_{i=3..n} (i mod 2) * (3 + floor((2n-1)/i) - ceiling((2n-1)/i) + floor(2n/i) - ceiling(2n/i) + floor((2n+1)/i) - ceiling((2n+1)/i)). - Wesley Ivan Hurt, Aug 10 2014

Sum_{k=1..n} a(k) ~ (n/2) * (3*log(n) + 6*gamma - 13 + 7*log(2)), where gamma is Euler's constant (A001620). - Amiram Eldar, Jan 19 2024

Extensions

More terms from Robert G. Wilson v, Jan 02 2002

More terms from Max Alekseyev, Apr 27 2010