OFFSET
1,3
COMMENTS
Term a(n) essentially records the run lengths of numbers of form 4k+3 encountered when starting from that node in binary tree A005940 which contains n, and by then traversing towards the root by iterating the map n -> A252463(n). The actual run lengths can be read from the exponents of primes in the prime factorization of A278222(A292383(m)), where m = min_{k=1..n} for which a(k) = a(n). In compound filter A292584 this is combined with similar information about the run lengths of the numbers of the form 4k+1 (A292585).
From Antti Karttunen, Sep 25 2017: (Start)
This follows from the interpretation of A053866 (A093709) as the characteristic function of squares and twice-squares. In binary tree A005940 each number is "born" by repeated applications of two functions: when we descend leftward we apply A003961, which shifts all prime factors of n one step towards larger primes. On the other hand, when we descend rightward the terms grow by doubling: n -> 2n (A005843). No square is ever of the form 4k+3, and for any square x, A003961(x) is also a square. Multiplying a square by 2 gives twice a square, and then multiplying by 2 again gives 4*square, which is also a square. In general, applying an even number of doubling steps in succession keeps a square as a square, while an odd number of doubling steps gives twice a square. Applying A003961 to any 2*square gives 3*(some square) which is always of the form 4k+3. Moreover, after any such "wrong turn" in A005940-tree no square nor twice a square can ever be encountered under any of the further descendants, because with this process it is impossible to find a pair for the lone prime factor now present. On the other hand, when turning left from any (2^2k)*s (where s is a square), one again gets a square of the form (3^2k)*A003961(s). All this implies that there are no numbers of the form 4k+3 in any trajectory leading to a square or twice a square in A005940-tree, while all trajectories to any other kind of number contain at least one number of the form 4k+3. Because each a(n) in this sequence contains enough information to count the 4k+3 numbers encountered on a A005940-trajectory to n (being 1 iff there are none), this filter matches A053866.
(End)
LINKS
EXAMPLE
When traversing from the root of binary tree A005940 from the node containing 7, one obtains path 7 -> 5 -> 3 -> 2 -> 1. Of these numbers, 7 and 3 are of the form 4k+3, while others are not, thus there are two separate runs of length 1: [1, 1]. On the other hand, when traversing from 15 as 15 -> 6 -> 3 -> 2 -> 1, again only two terms are of the form 4k+3: 15 and 3 and they are not next to each other, so we have the same two runs of one each: [1, 1], thus a(7) and a(15) are allotted the same value by the restricted growth sequence transform, which in this case is 3. Note that 3 occurs in this sequence for the first time at n=7, with A292383(7) = 5 and A278222(5) = 6 = 2^1 * 3^1, where those run lengths 1 and 1 are the prime exponents of 6.
PROG
(PARI)
allocatemem(2^30);
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om, invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om, invec[i], i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset, vec, bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t }; \\ Modified from code of M. F. Hasler
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ This function from Charles R Greathouse IV, Aug 17 2011
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1, 1]==2), f[1, 2] = 0); for (i=1, #f~, f[i, 1] = precprime(f[i, 1]-1)); factorback(f)};
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Sep 20 2017
STATUS
approved