A293522 -id:A293522

Search: a293522 -id:a293522

Displaying 1-5 of 5 results found.

page 1

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.

+10
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 ->oo} A293441(n+1)/a(n) ~= 0.770... (if it exists) and similarly lim_{n ->oo} 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).

KEYWORD

nonn

AUTHOR

Antti Karttunen and Michael De Vlieger, Oct 10 2017

STATUS

approved

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.

+10
9

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

(list; graph; refs; listen; history; text; internal format)

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.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 10 2017

STATUS

approved

A293521

Number of surviving (but not bifurcating) nodes at generation n in the binary tree of persistently squarefree numbers (see A293230).

+10
7

0, 1, 1, 3, 3, 2, 5, 9, 8, 11, 15, 24, 30, 42, 51, 76, 94, 126, 158, 217, 298, 403, 539, 731, 970, 1305, 1748, 2322, 3179, 4225, 5715, 7596, 10259, 13731, 18357, 24771, 33184, 44448, 59968, 80764, 107973, 145638, 195237, 262446, 352904, 474964, 637081, 856232, 1149966, 1543986, 2076534, 2789516

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

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

FORMULA

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

a(n) = A293518(n) + A293519(n). [even survivors + odd survivors.]

EXAMPLE

a(2) = 1 because in the binary tree illustrated in A293230, there is only one node at the level (namely, the node 6) that spawns just one offspring.

PROG

(PARI) \\ See program at A293520.

CROSSREFS

Cf. A293230, A293441, A293518, A293519, A293520, A293522.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 12 2017

STATUS

approved

A293520

Number of dying nodes (withering branches) at generation n in the binary tree of persistently squarefree numbers (A293230).

+10
6

0, 0, 0, 0, 1, 2, 2, 1, 2, 3, 3, 4, 9, 6, 13, 11, 21, 32, 40, 52, 60, 64, 90, 129, 169, 242, 321, 434, 549, 808, 1026, 1395, 1929, 2551, 3405, 4578, 6131, 8275, 11196, 14814, 20198, 26823, 36295, 48840, 65337, 87634, 118138, 158324, 212870, 287014

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

Provided that A293441 is strictly growing, then certainly a(n) < A293441(n), because only even nodes may die and A293441(n-1) gives the number of even nodes at level n.

LINKS

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

FORMULA

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

EXAMPLE

a(4) = 1 because in the binary tree illustrated in A293230, it is the only node 22 at the level 4 that does not generate any new buds as both 2*22 = 44 and 1+(2*22) = 45 are nonsquarefree numbers.

PROG

(PARI)

\\ Compute sequences A293230, A293520, A293521, A293522 at the same time:

allocatemem(2^30);

next_living_bud_or_zero(n) = if(issquarefree(n), n, 0);

write_counts(n, tops) = { my(w=0, s=0, b=0, k); for(i=1, #tops, if((tops[i]%2), if(issquarefree(1+(2*tops[i])), b++, s++), if(issquarefree(1+(2*tops[i])), s++, w++)); ); write("b293520.txt", n, " ", w); write("b293521.txt", n, " ", s); write("b293522.txt", n, " ", b); write("b293230.txt", n, " ", k=length(tops)); print1(k, ", "); }

tops_of_tree = [1];

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

write("b293520.txt", 0, " ", 0);

write("b293521.txt", 0, " ", 0);

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

print1(1, ", ");

for(n=1, 52, tops_of_tree = nextA293230generation(tops_of_tree); write_counts(n, tops_of_tree); );

CROSSREFS

Cf. A293230, A293441, A293521, A293522.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Oct 12 2017

STATUS

approved

A293440

First differences of A293230: how many more alive nodes there are in generation n+1 than in generation n in the binary tree of persistently squarefree numbers.

+10
2

1, 1, 2, 2, 2, 3, 3, 4, 7, 9, 14, 17, 18, 30, 37, 53, 68, 82, 116, 149, 201, 289, 390, 510, 701, 921, 1241, 1682, 2277, 2990, 4054, 5489, 7247, 9778, 13222, 17684, 23849, 32146, 42930, 57828, 77679, 104443, 140343, 188387, 253322, 339990, 456855, 614187, 825548, 1108788, 1489668

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

FORMULA

a(n) = A293230(1+n)-A293230(n).

a(n) = A293522(n) - A293520(n). [Equal to the number of bifurcating nodes minus the number of withering nodes.]

PROG

(Scheme) (define (A293440 n) (- (A293230 (+ 1 n)) (A293230 n)))

CROSSREFS

Cf. A293230, A293520, A293521, A293522, A293441.