|
|
A066272
|
|
Number of anti-divisors of n.
|
|
142
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
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
|
|
EXAMPLE
|
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.
|
|
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:
nops(antidivisors(n)) ;
end proc:
|
|
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 *)
|
|
PROG
|
(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 && t<n, concat(concat(divisors(2*n-1), divisors(2*n+1)), 2*divisors(n)))
(Python)
from sympy import divisors
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|