A293517 -id:A293517 - cp's OEIS frontend

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.

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

Offset: 0

Antti Karttunen, Oct 10 2017

nonn

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.

Cf. A293230, A293520, A293521, A293522.

Cf. A293517 (the first differences), A293518, A293519.

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

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

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

(define (A293441 n) (add (lambda (k) (* (A000035 k) (abs (A293233 k)))) (A000079 n) (+ -1 (A000079 (+ 1 n)))))

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

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

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

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

Original entry on oeis.org

0, 0, 0, 1, 1, 0, 2, 3, 2, 3, 3, 8, 10, 11, 17, 20, 31, 38, 46, 67, 90, 116, 160, 220, 280, 397, 509, 685, 927, 1280, 1663, 2248, 3056, 4050, 5383, 7339, 9714, 13029, 17714, 23738, 31791, 42793, 57473, 77175, 103839, 140100, 187495, 252068, 338257, 454325, 611101, 820924

Offset: 0

Antti Karttunen, Oct 16 2017

nonn

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

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

\\ A naive algorithm (see A293518 for a better program):
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); };
{ countsA293441 = 1; countsA293519 = 0; k=1; n=3; while(n <= 1+up_to,if(!bitand(n-1,n-2), write("b293441.txt", k, " ", countsA293441); write("b293519.txt", k, " ", countsA293519); print1(countsA293519,", "); countsA293441 = 0; countsA293519 = 0; k++); if(is_persistently_squarefree(n,2),countsA293441++; if(!issquarefree(1+(2*n)),countsA293519++)); n += 2); }

(define (A293519 n) (add (lambda (k) (* (if (and (= 1 (A008966 (+ k k))) (= 0 (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)) * [1==A008966(2*k)] * [0==A008966(1+2*k)].
A293518(n) + a(n) = A293521(n).
A293518(n) - a(n) = A293517(n).

A293428 a(0) = 1; and for n > 0, a(n) = a(n-1) + (A008966(4n+1) - A107078(4n+3)).

Original entry on oeis.org

1, 2, 2, 3, 4, 5, 4, 5, 6, 7, 8, 8, 8, 9, 10, 10, 11, 12, 12, 13, 13, 14, 15, 16, 16, 17, 18, 19, 20, 20, 20, 20, 21, 21, 22, 23, 23, 24, 24, 25, 26, 27, 26, 26, 27, 28, 29, 29, 30, 31, 32, 32, 33, 34, 35, 36, 36, 37, 38, 39, 39, 39, 40, 41, 42, 42, 43, 44, 44, 44, 45, 46, 46, 47, 47, 48, 49, 50, 50, 51, 52, 52, 53, 53

Offset: 0

Antti Karttunen, Oct 16 2017

nonn

After a(0)=1, each term a(n) is either (a) one more than its predecessor, in case 4n+1 and 4n+3 are both squarefree, (b) stays same if only the other one is squarefree, or (c) decreases by one if neither 4n+1 nor 4n+3 are squarefree.

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

Cf. A008966, A107078, A293229, A293429.

Cf. also A293517.

a(0) = 1; and for n > 0, a(n) = a(n-1) + -1+(A008966(4n+1)+A008966(4n+3)).

Or for n > 0, a(n) = a(n-1) + (A008966(4n+1) - A107078(4n+3)).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

PARI

Scheme

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

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

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

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Scheme

Formula

A293428 a(0) = 1; and for n > 0, a(n) = a(n-1) + (A008966(4n+1) - A107078(4n+3)).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula