cp's OEIS Frontend

A293230 a(n) is the number of integers 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 A293230 #56 Sep 18 2023 18:42:36
%S A293230 1,2,3,5,7,9,12,15,19,26,35,49,66,84,114,151,204,272,354,470,619,820,
%T A293230 1109,1499,2009,2710,3631,4872,6554,8831,11821,15875,21364,28611,
%U A293230 38389,51611,69295,93144,125290,168220,226048,303727,408170,548513,736900,990222,1330212,1787067,2401254,3226802,4335590,5825258
%N A293230 a(n) is the number of integers 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 A293230 Question: Is this sequence monotonic? If monotonic, then it certainly cannot settle to zero, which implies that A293430 is infinite and that there are nonzero terms arbitrary far in A293233.
%C A293230 If there are no zero terms, then in a simple binary tree illustrated below (where the left hand child is obtained as 2*parent, and the right hand child is 1 + 2*parent) there are arbitrary long trajectories starting from 1 that consist squarefree numbers (A005117) only. All numbers k that are in such trajectories are marked as <k> (terms of A293430). a(n) = the number of marked numbers at level n, where level 0 is the root 1, level 1 has nodes 2 and 3, level 2 nodes 5, 6, 7, etc.
%C A293230                                     <1>
%C A293230                                      |
%C A293230                  .................../ \...................
%C A293230                 <2>                                     <3>
%C A293230        4......../ \.......<5>                 <6>......./ \.......<7>
%C A293230       / \                 / \                 / \                 / \
%C A293230      /   \               /   \               /   \               /   \
%C A293230     /     \             /     \             /     \             /     \
%C A293230    /       \           /       \           /       \           /       \
%C A293230   8         9        <10>     <11>        12      <13>       <14>     <15>
%C A293230 16 17     18 19    20  <21> <22> <23>   24  25  <26>  27   28 <29> <30> <31>
%C A293230 etc.
%C A293230 ---
%F A293230 a(n) = Sum_{k=2^n..2^(1+n)-1} abs(A293233(k)).
%F A293230 For n >= 1, a(n) = A293441(n) + A293441(n-1).
%F A293230 a(n) = A293520(n) + A293521(n) + A293522(n). [sum of number of withering, surviving and bifurcating nodes at each level.]
%F A293230 a(n) = A293520(n) + (A293518(n) + A293519(n)) + A293522(n).
%F A293230 It seems that lim_{n ->oo} A293441(n+1)/a(n) ~= 0.770... (if it exists) and similarly lim_{n ->oo} a(n+1)/a(n) ~= 1.34...
%e A293230 In range [2^0 .. (2^1)-1] = [1], all terms (namely 1) are in A293430, thus a(0) = 1.
%e A293230 In range [2^1 .. (2^2)-1] = [2 .. 3] all terms are in A293430, thus a(1) = 2.
%e A293230 In range [2^2 .. (2^3)-1] = [4 .. 7] the terms 5, 6, 7 are in A293430 (because they themselves are squarefree and when applying x -> floor(x/2) to them, give either 2 or 3, numbers that are also included in A293430), thus a(2) = 3.
%t A293230 Table[Count[Range[2^n, (2^(n + 1)) - 1], _?(AllTrue[Table[Floor[#/2^e], {e, 0, n}], SquareFreeQ] &)], {n, 0, 20}] (* _Michael De Vlieger_, Oct 10 2017 *)
%o A293230 (PARI)
%o A293230 \\ A naive algorithm that computes A293233, A293430 and A293230 at the same time:
%o A293230 allocatemem(2^30);
%o A293230 up_to_level = 23;
%o A293230 up_to = (2^(1+up_to_level))-1;
%o A293230 v293233 = vector(up_to);
%o A293230 v293233[1] = 1;
%o A293230 write("b293430.txt", 1, " ", 1);
%o A293230 countsA293230 = 1; kA293430 = 2; for(n=2,up_to,if(!bitand(n,n-1), print1(countsA293230,", "); countsA293230 = 0); v293233[n] = moebius(n)* v293233[n\2];if(v293233[n],write("b293430.txt", kA293430, " ", n); kA293430++; countsA293230++)); print1(countsA293230);
%o A293230 (PARI)
%o A293230 \\ Much faster algorithm:
%o A293230 allocatemem(2^30);
%o A293230 next_living_bud_or_zero(n) = if(issquarefree(n),n,0);
%o A293230 nextA293230generation(tops) = { my(new_tops = vecsort(vector(2*#tops,i,next_living_bud_or_zero((2*tops[(i+1)\2])+(i%2))),,8)); if(0==new_tops[1], vector(#new_tops-1,i,new_tops[1+i]), new_tops); }
%o A293230 tops_of_tree = [1];
%o A293230 write("b293230.txt", 0, " ", 1);
%o A293230 print1(1, ", ");
%o A293230 for(n=1,64,tops_of_tree = nextA293230generation(tops_of_tree); write("b293230.txt", n, " ", k = length(tops_of_tree)); print1(k, ", "));
%Y A293230 Cf. A005117, A293233, A293430, A293441, A293518, A293519, A293520, A293521, A293522.
%Y A293230 Cf. A293440 (the first differences).
%K A293230 nonn
%O A293230 0,2
%A A293230 _Antti Karttunen_ and _Michael De Vlieger_, Oct 10 2017