cp's OEIS Frontend

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.

%I A293441 #44 Jan 20 2023 22:51:11
%S A293441 1,1,2,3,4,5,7,8,11,15,20,29,37,47,67,84,120,152,202,268,351,469,640,
%T A293441 859,1150,1560,2071,2801,3753,5078,6743,9132,12232,16379,22010,29601,
%U A293441 39694,53450,71840,96380,129668,174059,234111,314402,422498,567724,762488,1024579,1376675,1850127,2485463,3339795
%N 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.
%C A293441 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.
%C A293441 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.
%F A293441 a(n) = Sum_{k=2^n..2^(1+n)-1} A000035(k)*abs(A293233(k)).
%F A293441 For n >= 1, A293230(n) = a(n) + a(n-1).
%F A293441 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.]
%F A293441 For n >= 1, if a(n) > a(n-1) then a(n) > A293520(n). [Because only even nodes may die.]
%F A293441 A293522(n) <= a(n) <= A293521(n) + A293522(n). [Because no even node can bifurcate but all odd nodes either survive or bifurcate.]
%t A293441 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 *)
%o A293441 (PARI)
%o A293441 \\ A naive algorithm:
%o A293441 up_to_level = 28;
%o A293441 up_to = (2^(1+up_to_level));
%o A293441 is_persistently_squarefree(n,base) = { while(n>1, if(!issquarefree(n),return(0)); n \= base); (1); };
%o A293441 is_oddA293430(n) = ((n%2)&&is_persistently_squarefree(n,2));
%o A293441 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++));
%o A293441 (PARI)
%o A293441 \\ Faster way, compute A293441, A293518 and A293519 at the same time:
%o A293441 allocatemem(2^30);
%o A293441 next_living_bud_or_zero(n) = if(issquarefree(n),n,0);
%o A293441 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); }
%o A293441 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, ", ");}
%o A293441 tops_of_tree = [1];
%o A293441 write("b293441.txt", 0, " ", 1);
%o A293441 write("b293518.txt", 0, " ", 0);
%o A293441 write("b293519.txt", 0, " ", 0);
%o A293441 print1(1, ", ");
%o A293441 for(n=1,51,tops_of_tree = nextA293230generation(tops_of_tree); writeA293441etc_counts(n,tops_of_tree););
%o A293441 (Scheme)
%o A293441 (define (A293441 n) (add (lambda (k) (* (A000035 k) (abs (A293233 k)))) (A000079 n) (+ -1 (A000079 (+ 1 n)))))
%Y A293441 Cf. A293230, A293520, A293521, A293522.
%Y A293441 Cf. A293517 (the first differences), A293518, A293519.
%K A293441 nonn
%O A293441 0,3
%A A293441 _Antti Karttunen_, Oct 10 2017