A293441 -id:A293441 - 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.

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

Offset: 0

Antti Karttunen and Michael De Vlieger, Oct 10 2017

nonn

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  (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.
---

			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.

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

Cf. A293440 (the first differences).

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

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

\\ 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, ", "));

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...

A293430 Persistently squarefree numbers for base-2 shifting: Numbers n such that all terms in finite set [n, floor(n/2), floor(n/4), floor(n/8), ..., 1] are squarefree.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 21, 22, 23, 26, 29, 30, 31, 42, 43, 46, 47, 53, 58, 59, 61, 62, 85, 86, 87, 93, 94, 95, 106, 107, 118, 119, 122, 123, 170, 173, 174, 186, 187, 190, 191, 213, 214, 215, 237, 238, 239, 246, 247, 341, 346, 347, 349, 373, 374, 381, 382, 383, 426, 427, 429, 430, 431, 474, 478, 479

Offset: 1

Antti Karttunen and Michael De Vlieger, Oct 10 2017

nonn

Question: Is this sequence infinite? (My guess: yes). This is equivalent to questions asked in A293230. See also comments at A293441 and A293517.

For any odd n that is present, 2n is also present.

			For 479 we see that 479 is prime (thus squarefree, in A005117), [479/2] = 239 is also a prime, [239/2] = 119 = 7*17 (a squarefree composite), [119/2] = 59 (a prime), [59/2] = 29 (a prime), [29/2] = 14 = 2*7 (a squarefree composite), [14/2] = 7 (a prime), [7/2] = 3 (a prime), [3/2] = 1 (the end of halving process 1 is also squarefree), thus all the values obtained by repeated halving were squarefree and 479 is a member of this sequence. Here [ ] stands for taking floor.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Marked terms in the binary tree illustration of A293230.
Subsequence of A293427 (thus also of A003754 and of A005117).
Positions of nonzero terms in A293233.
Cf. A293441, A293517, A293523 (for floor(n/3^k) analog), A293437 (for a subsequence).

With[{s = Fold[Append[#1, MoebiusMu[#2] #1[[Floor[#2/2]]]] &, {1}, Range[2, 480]]}, Flatten@ Position[s, ?(# != 0 &)]] (* _Michael De Vlieger, Oct 10 2017 *)

is_persistently_squarefree(n,base) = { while(n>1, if(!issquarefree(n),return(0)); n \= base); (1); };
isA293430(n) = is_persistently_squarefree(n,2);
n=0; k=1; while(k <= 10000, n=n+1; if(isA293430(n),write("b293430.txt", k, " ", n);k=k+1)); \\ Antti Karttunen, Oct 11 2017

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 12 2017

nonn

			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.

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

PARI
```
\\ See program at A293520.
```

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

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

A293517 a(n) = A293518(n) - A293519(n); how many more surviving even nodes than surviving (but not bifurcating) odd nodes there are at generation n in the binary tree of persistently squarefree numbers.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 3, 4, 5, 9, 8, 10, 20, 17, 36, 32, 50, 66, 83, 118, 171, 219, 291, 410, 511, 730, 952, 1325, 1665, 2389, 3100, 4147, 5631, 7591, 10093, 13756, 18390, 24540, 33288, 44391, 60052, 80291, 108096, 145226, 194764, 262091, 352096, 473452, 635336, 854332, 1147668

Offset: 0

Antti Karttunen, Oct 16 2017

nonn

As long as there are at least as many surviving even than surviving (but not bifurcating) odd nodes at each generation in the tree of persistently squarefree numbers (see illustration in A293230), this sequence also stays nonnegative, and being also the first differences of A293441 guarantees its monotonicity. If A293441 is monotonic, then A293230 is also, which in turn implies also that A293430 has infinite number of terms and that there will be nonzero terms arbitrary far in A293233.

The surviving children of even vertices are all of the form 4k+1, while the surviving children (those without an odd sibling) of odd vertices are all of the form 4k+2.

Cf. A293230, A293233, A293430, A293518, A293519.
First differences of A293441.
Cf. also A293428.

(define (A293517 n) (- (A293518 n) (A293519 n)))

a(n) = A293518(n) - A293519(n).

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

A293518 Number of surviving even nodes at generation n in the binary tree of persistently squarefree numbers (see A293230).

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 3, 6, 6, 8, 12, 16, 20, 31, 34, 56, 63, 88, 112, 150, 208, 287, 379, 511, 690, 908, 1239, 1637, 2252, 2945, 4052, 5348, 7203, 9681, 12974, 17432, 23470, 31419, 42254, 57026, 76182, 102845, 137764, 185271, 249065, 334864, 449586, 604164, 811709, 1089661, 1465433, 1968592

Offset: 0

Antti Karttunen, Oct 16 2017

nonn

			a(3) = 2 because in the binary tree illustrated in A293230, there are two even nodes at the level 3 (namely, the nodes 10 and 14) that spawn just one offspring each.

Cf. A008966, A293230, A293233, A293517, A293519, A293521.

\\ Compute the sequences 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););

(define (A293518 n) (add (lambda (k) (* (if (and (= 0 (A008966 (+ k k))) (= 1 (A008966 (+ 1 k k)))) 1 0) (abs (A293233 k)))) (A000079 n) (+ -1 (A000079 (+ 1 n)))))
;; Implements sum_{i=lowlim..uplim} intfun(i)
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))

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

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 12 2017

nonn

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.

			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.

Cf. A293230, A293441, A293521, A293522.

\\ Compute sequences A293230, A293520, A293521, A293522 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); }
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););

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

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

Original entry on oeis.org

1, 1, 2, 2, 3, 5, 5, 5, 9, 12, 17, 21, 27, 36, 50, 64, 89, 114, 156, 201, 261, 353, 480, 639, 870, 1163, 1562, 2116, 2826, 3798, 5080, 6884, 9176, 12329, 16627, 22262, 29980, 40421, 54126, 72642, 97877, 131266, 176638, 237227, 318659, 427624, 574993, 772511, 1038418, 1395802

Offset: 0

Antti Karttunen, Oct 12 2017

nonn

Bifurcating node is one that branches to two alive nodes in the next generation (level) of the tree.

			a(2) = 2 because in the binary tree illustrated in A293230, there are two nodes at the level 2 (namely 5 and 7) that spawn two offspring each.

Cf. A293230, A293441, A293520, A293521.

PARI
```
\\ See program at A293520.
```

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

a(n) <= A293441(n). [Because no even node can bifurcate.]

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.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 12 2017

nonn

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

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

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.]

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A293430 Persistently squarefree numbers for base-2 shifting: Numbers n such that all terms in finite set [n, floor(n/2), floor(n/4), floor(n/8), ..., 1] are squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A293517 a(n) = A293518(n) - A293519(n); how many more surviving even nodes than surviving (but not bifurcating) odd nodes there are at generation n in the binary tree of persistently squarefree numbers.

Views

Author

Keywords

Comments

Crossrefs

Programs

Scheme

Formula

A293518 Number of surviving even nodes at generation n in the binary tree of persistently squarefree numbers (see A293230).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Scheme

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Crossrefs

Programs

Scheme

Formula