|
%I #56 Sep 18 2023 18:42:36
%S 1,2,3,5,7,9,12,15,19,26,35,49,66,84,114,151,204,272,354,470,619,820,
%T 1109,1499,2009,2710,3631,4872,6554,8831,11821,15875,21364,28611,
%U 38389,51611,69295,93144,125290,168220,226048,303727,408170,548513,736900,990222,1330212,1787067,2401254,3226802,4335590,5825258
%N 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 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 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 <1>
%C |
%C .................../ \...................
%C <2> <3>
%C 4......../ \.......<5> <6>......./ \.......<7>
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 8 9 <10> <11> 12 <13> <14> <15>
%C 16 17 18 19 20 <21> <22> <23> 24 25 <26> 27 28 <29> <30> <31>
%C etc.
%C ---
%F a(n) = Sum_{k=2^n..2^(1+n)-1} abs(A293233(k)).
%F For n >= 1, a(n) = A293441(n) + A293441(n-1).
%F a(n) = A293520(n) + A293521(n) + A293522(n). [sum of number of withering, surviving and bifurcating nodes at each level.]
%F a(n) = A293520(n) + (A293518(n) + A293519(n)) + A293522(n).
%F 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 In range [2^0 .. (2^1)-1] = [1], all terms (namely 1) are in A293430, thus a(0) = 1.
%e In range [2^1 .. (2^2)-1] = [2 .. 3] all terms are in A293430, thus a(1) = 2.
%e 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 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 (PARI)
%o \\ A naive algorithm that computes A293233, A293430 and A293230 at the same time:
%o allocatemem(2^30);
%o up_to_level = 23;
%o up_to = (2^(1+up_to_level))-1;
%o v293233 = vector(up_to);
%o v293233[1] = 1;
%o write("b293430.txt", 1, " ", 1);
%o 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 (PARI)
%o \\ Much faster algorithm:
%o allocatemem(2^30);
%o next_living_bud_or_zero(n) = if(issquarefree(n),n,0);
%o 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 tops_of_tree = [1];
%o write("b293230.txt", 0, " ", 1);
%o print1(1, ", ");
%o for(n=1,64,tops_of_tree = nextA293230generation(tops_of_tree); write("b293230.txt", n, " ", k = length(tops_of_tree)); print1(k, ", "));
%Y Cf. A005117, A293233, A293430, A293441, A293518, A293519, A293520, A293521, A293522.
%Y Cf. A293440 (the first differences).
%K nonn
%O 0,2
%A _Antti Karttunen_ and _Michael De Vlieger_, Oct 10 2017
|
