login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A271834 a(n) = 2^n - Sum_{m=0..n} binomial(n/GCD(n,m),m/GCD(n,m)) = 2^n - A082906. 1
0, 0, 0, 4, 0, 42, 0, 116, 162, 730, 0, 2458, 0, 11494, 16890, 32628, 0, 180960, 0, 554994, 931476, 2800534, 0, 11005898, 6643750, 43946838, 44738892, 136580910, 0, 720879712, 0, 2147450740, 3250382916, 10923409738, 11517062060, 45683761528, 0, 172783692982 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

Compared to A082906, this sequence shows better the drop from 2^n upon replacing every binomial(n,m) in the Newton's expansion of (1+1)^n by the 'reduced' binomial(n/GCD(n,m),m/GCD(n,m)). For n > 1, a(n) is zero if and only if n is prime (no reduction, no drop). The ratio r(n) = a(n)/2^n is always smaller than 1 and presents considerable excursions. For composite n up to 5000, the minimum of 0.01471... occurs for n = 4489, and the maximum of 0.80849... occurs for n = 2310. This apparently large relative difference is actually surprisingly small: on log_2 scale it amounts to just about 5.78; a tiny fraction compared to the full scale, given by the values of n for the extrema. This insight suggests the following conjecture: there exists an average ratio r, defined as r = lim_{n->infinity} Sum_{m=1..n} r(m)/n. Its value appears to be approximately 0.3915+-0.0010, which can be interpreted as the average drop in a binomial value upon the 'reduction' of its arguments.

LINKS

Stanislav Sykora, Table of n, a(n) for n = 1..1000

Stanislav Sykora, Ratios A271834(n)/2^n for n=1..5000

FORMULA

For prime p, a(p) = 0.

For any n, a(n) < 2^n - n(n+1)/2.

EXAMPLE

Sum_{m=1..2500} r(m)/2500 = 0.391460...

Sum_{m=2501..5000} r(m)/2500 = 0.391975...

Sum_{m=1..5000} r(m)/5000 = 0.391718...

MAPLE

A271834:=n->2^n-add(binomial(n/gcd(n, m), m/gcd(n, m)), m=0..n): seq(A271834(n), n=1..50); # Wesley Ivan Hurt, Apr 19 2016

MATHEMATICA

Table[2^n - Sum[Binomial[n/GCD[n, m], m/GCD[n, m]], {m, 0, n}], {n, 40}] (* Wesley Ivan Hurt, Apr 19 2016 *)

PROG

(PARI) bcg(n, m)=binomial(n/gcd(n, m), m/gcd(n, m));

a = vector(1000, n, 2^n-vecsum(vector(n+1, m, bcg(n, m-1))))

CROSSREFS

Cf. A082905, A082906.

Sequence in context: A271120 A174083 A123936 * A138546 A019217 A221757

Adjacent sequences:  A271831 A271832 A271833 * A271835 A271836 A271837

KEYWORD

nonn,easy

AUTHOR

Stanislav Sykora, Apr 19 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 25 20:28 EDT 2017. Contains 289797 sequences.