A271834 - OEIS

%I #38 Aug 01 2019 04:09:52

%S 0,0,0,4,0,42,0,116,162,730,0,2458,0,11494,16890,32628,0,180960,0,

%T 554994,931476,2800534,0,11005898,6643750,43946838,44738892,136580910,

%U 0,720879712,0,2147450740,3250382916,10923409738,11517062060,45683761528,0,172783692982

%N a(n) = 2^n - Sum_{m=0..n} binomial(n/gcd(n,m), m/gcd(n,m)) = 2^n - A082906.

%C 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.

%H Stanislav Sykora, <a href="/A271834/b271834.txt">Table of n, a(n) for n = 1..1000</a>

%H Stanislav Sykora, <a href="/A271834/a271834.txt">Ratios A271834(n)/2^n for n=1..5000</a>

%F For prime p, a(p) = 0.

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

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

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

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

%p 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

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

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

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

%Y Cf. A082905, A082906.

%K nonn,easy

%O 1,4

%A _Stanislav Sykora_, Apr 19 2016