A292583 Restricted growth sequence transform of A278222(A292383(n)); a filter related to runs of numbers of the form 4k+3 encountered on trajectories of A005940-tree.

1, 1, 2, 1, 2, 2, 3, 1, 1, 2, 4, 2, 4, 3, 3, 1, 4, 1, 5, 2, 2, 4, 6, 2, 1, 4, 2, 3, 6, 3, 7, 1, 3, 4, 4, 1, 7, 5, 5, 2, 7, 2, 8, 4, 2, 6, 9, 2, 1, 1, 5, 4, 9, 2, 3, 3, 4, 6, 10, 3, 10, 7, 3, 1, 3, 3, 11, 4, 5, 4, 12, 1, 12, 7, 2, 5, 4, 5, 13, 2, 1, 7, 14, 2, 5, 8, 7, 4, 14, 2, 4, 6, 6, 9, 6, 2, 14, 1, 15, 1, 14, 5, 16, 4, 3

Offset: 1

Author

Antti Karttunen, Sep 20 2017

Keywords

• nonn

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)

For all i, j: a(i) = a(j) => A053866(i) = A053866(j).

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)

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Index entries for sequences computed from indices in prime factorization

Crossrefs

Cf. A005940, A252463, A278222, A292377, A292383, A292582, A292584, A292585, A292586, A292588.

Cf. A028982 (positions of ones), A053866 (A093709).

Programs

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)};
A278222(n) = A046523(A005940(1+n));
A252463(n) = if(!(n%2),n/2,A064989(n));
A292383(n) = if(1==n,0,(if(3==(n%4),1,0)+(2*A292383(A252463(n)))));
write_to_bfile(1,rgs_transform(vector(16384,n,A278222(A292383(n)))),"b292583_upto16384.txt");