login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 12
1, 2, 3, 5, 7, 9, 12, 15, 19, 26, 35, 49, 66, 84, 114, 151, 204, 272, 354, 470, 619, 820, 1109, 1499, 2009, 2710, 3631, 4872, 6554, 8831, 11821, 15875, 21364, 28611, 38389, 51611, 69295, 93144, 125290, 168220, 226048, 303727, 408170, 548513, 736900, 990222, 1330212, 1787067, 2401254, 3226802, 4335590, 5825258 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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.

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.

                                    <1>

                                     |

                 .................../ \...................

                <2>                                     <3>

       4......../ \.......<5>                 <6>......./ \.......<7>

      / \                 / \                 / \                 / \

     /   \               /   \               /   \               /   \

    /     \             /     \             /     \             /     \

   /       \           /       \           /       \           /       \

  8         9        <10>     <11>        12      <13>       <14>     <15>

16 17     18 19    20  <21> <22> <23>   24  25  <26>  27   28 <29> <30> <31>

etc.

---

LINKS

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

FORMULA

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

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

a(n) = A293520(n) + A293521(n) + A293522(n). [sum of number of withering, surviving and bifurcating nodes at each level.]

a(n) = A293520(n) + (A293518(n) + A293519(n)) + A293522(n).

It seems that lim n ->infinity A293441(n+1)/a(n) ~= 0.770... (if it exists) and similarly lim n ->infinity a(n+1)/a(n) ~= 1.34...

EXAMPLE

In range [2^0 .. (2^1)-1] = [1], all terms (namely 1) are in A293430, thus a(0) = 1.

In range [2^1 .. (2^2)-1] = [2 .. 3] all terms are in A293430, thus a(1) = 2.

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.

MATHEMATICA

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 *)

PROG

(PARI)

\\ A naive algorithm that computes A293233, A293430 and A293230 at the same time:

allocatemem(2^30);

up_to_level = 23;

up_to = (2^(1+up_to_level))-1;

v293233 = vector(up_to);

v293233[1] = 1;

write("b293430.txt", 1, " ", 1);

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);

(PARI)

\\ Much faster algorithm:

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%2))), , 8)); if(0==new_tops[1], vector(#new_tops-1, i, new_tops[1+i]), new_tops); }

tops_of_tree = [1];

write("b293230.txt", 0, " ", 1);

print1(1, ", ");

for(n=1, 64, tops_of_tree = nextA293230generation(tops_of_tree); write("b293230.txt", n, " ", k = length(tops_of_tree)); print1(k, ", "));

CROSSREFS

Cf. A005117, A293233, A293430, A293441, A293518, A293519, A293520, A293521, A293522.

Cf. A293440 (the first differences).

Sequence in context: A062441 A059290 A309881 * A133231 A235111 A228896

Adjacent sequences:  A293227 A293228 A293229 * A293231 A293232 A293233

KEYWORD

nonn

AUTHOR

Antti Karttunen and Michael De Vlieger, Oct 10 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 07:28 EST 2020. Contains 332067 sequences. (Running on oeis4.)