A293441 a(n) is the number of odd numbers k in range [2^n, (2^(n+1))-1] such that all terms in finite sequence [k, floor(k/2), floor(k/4), floor(k/8), ..., 1] are squarefree.

1, 1, 2, 3, 4, 5, 7, 8, 11, 15, 20, 29, 37, 47, 67, 84, 120, 152, 202, 268, 351, 469, 640, 859, 1150, 1560, 2071, 2801, 3753, 5078, 6743, 9132, 12232, 16379, 22010, 29601, 39694, 53450, 71840, 96380, 129668, 174059, 234111, 314402, 422498, 567724, 762488, 1024579, 1376675, 1850127, 2485463, 3339795

Offset

0,3

Comments

For n > 0, a(n-1) is the number of even numbers in the same range satisfying the same condition. This follows because the alive even nodes in any generation (or level) of the binary tree illustrated in A293230 are all offspring of the odd nodes of the previous generation. (Even nodes cannot have even offspring simply because no number divisible by 4 can be squarefree). On the other hand, each odd node has an alive even child, because if an odd number k is squarefree, then 2k is squarefree as well.

The necessary and sufficient condition for this sequence to stay monotonic is that A293517(n) = A293518(n) - A293519(n) >= 0 (because A293517(n) = a(1+n) - a(n) also), in other words, that for every generation #{even nodes that survive} >= #{odd nodes that just survive, i.e., do not bifurcate}. If this sequence is monotonic then surely A293230 is also.

Links

Table of n, a(n) for n=0..51.

Formula

a(n) = Sum_{k=2^n..2^(1+n)-1} A000035(k)*abs(A293233(k)).

For n >= 1, A293230(n) = a(n) + a(n-1).

For n >= 1, if a(n) > a(n-1) then A293230(n) > A293230(n-1) and thus also A293522(n) > A293520(n). [If this sequence is monotonic, then so is A293230.]

For n >= 1, if a(n) > a(n-1) then a(n) > A293520(n). [Because only even nodes may die.]

A293522(n) <= a(n) <= A293521(n) + A293522(n). [Because no even node can bifurcate but all odd nodes either survive or bifurcate.]

Mathematica

Table[Count[Range[2^n + 1, (2^(n + 1)) - 1, 2], _?(AllTrue[ Table[Floor[#/2^e], {e, 0, n}], SquareFreeQ] &)], {n, 0, 20}] (* Michael De Vlieger, Oct 10 2017 *)

Prog

(PARI)
\\ A naive algorithm:
up_to_level = 28;
up_to = (2^(1+up_to_level));
is_persistently_squarefree(n, base) = { while(n>1, if(!issquarefree(n), return(0)); n \= base); (1); };
is_oddA293430(n) = ((n%2)&&is_persistently_squarefree(n, 2));
countsA293441 = 1; k=1; for(n=2, up_to, if(!bitand(n, n-1), write("b293441.txt", k, " ", countsA293441); print1(countsA293441, ", "); countsA293441 = 0; k++); if(is_oddA293430(n), countsA293441++));
(PARI)
\\ Faster way, compute A293441, A293518 and A293519 at the same time:
allocatemem(2^30);
next_living_bud_or_zero(n) = if(issquarefree(n), n, 0);
nextA293230generation(tops) = { my(new_tops = vecsort(vector(2*#tops, i, next_living_bud_or_zero((2*tops[(i+1)\2])+((i+1)%2))), , 8)); if(0==new_tops[1], vector(#new_tops-1, i, new_tops[1+i]), new_tops); }
writeA293441etc_counts(n, tops) = { my(os=0, es=0, k=0); for(i=1, #tops, if((tops[i]%2), k++; if(!issquarefree(1+(2*tops[i])), os++), if(issquarefree(1+(2*tops[i])), es++)); ); write("b293441.txt", n, " ", k); write("b293518.txt", n, " ", es); write("b293519.txt", n, " ", os); print1(k, ", "); }
tops_of_tree = [1];
write("b293441.txt", 0, " ", 1);
write("b293518.txt", 0, " ", 0);
write("b293519.txt", 0, " ", 0);
print1(1, ", ");
for(n=1, 51, tops_of_tree = nextA293230generation(tops_of_tree); writeA293441etc_counts(n, tops_of_tree); );
(Scheme)
(define (A293441 n) (add (lambda (k) (* (A000035 k) (abs (A293233 k)))) (A000079 n) (+ -1 (A000079 (+ 1 n)))))

Crossrefs

Cf. A293230, A293520, A293521, A293522.

Cf. A293517 (the first differences), A293518, A293519.

Sequence in context: A238484 A241340 A326667 * A306203 A111795 A046098

Adjacent sequences: A293438 A293439 A293440 * A293442 A293443 A293444

Keyword

nonn

Author

Antti Karttunen, Oct 10 2017

Status

approved