A292583 - OEIS

%I #45 Jun 03 2018 02:02:00

%S 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,

%T 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,

%U 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

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

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

%C From _Antti Karttunen_, Sep 25 2017: (Start)

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

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

%C (End)

%H Antti Karttunen, <a href="/A292583/b292583.txt">Table of n, a(n) for n = 1..16384</a>

%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>

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

%o (PARI)

%o allocatemem(2^30);

%o 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; };

%o write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }

%o 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_

%o 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

%o 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)};

%o A278222(n) = A046523(A005940(1+n));

%o A252463(n) = if(!(n%2),n/2,A064989(n));

%o A292383(n) = if(1==n,0,(if(3==(n%4),1,0)+(2*A292383(A252463(n)))));

%o write_to_bfile(1,rgs_transform(vector(16384,n,A278222(A292383(n)))),"b292583_upto16384.txt");

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

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

%K nonn

%O 1,3

%A _Antti Karttunen_, Sep 20 2017