cp's OEIS Frontend

A295887 Filter sequence combining A003557(n) and A173557(n); the restricted growth sequence transform of A291756.

%I A295887 #32 Feb 16 2025 08:33:52
%S A295887 1,1,2,3,4,2,5,6,7,4,8,9,10,5,11,12,13,7,14,15,10,8,16,17,18,10,19,20,
%T A295887 21,11,22,23,24,13,25,26,27,14,25,28,29,10,30,31,32,16,33,34,35,18,36,
%U A295887 37,38,19,29,39,27,21,40,41,42,22,43,44,45,24,46,47,48,25,49,50,51,27,52,53,42,25,54,55,56,29,57,37,58,30,59,60,61,32,51,62,42,33,51
%N A295887 Filter sequence combining A003557(n) and A173557(n); the restricted growth sequence transform of A291756.
%C A295887 First define function f(n) = (1/2)*(2 + ((A003557(n) + A173557(n))^2) - A003557(n) - 3*A173557(n)), or in short, f(n) = P(A003557(n),  A173557(n)), where P(n,k) is triangular table sequence A000027 used as an injective N x N -> N pairing function. Then apply the restricted growth sequence transform to the sequence f(1), f(2), f(3), ... See the example-section.
%C A295887 This is also the restricted growth sequence transform of sequence A291756, as A291756(n) = P(A003557(n), A000010(n)), where again P(n,k) is sequence A000027 used as a pairing function. Given either an ordered pair (A003557(n),A000010(n)) or (A003557(n),A173557(n)), the other one can be computed because A000010(n) = A003557(n)*A173557(n).
%C A295887 Note that the exact pairing function P used is not important, as long as it provides an injective mapping N x N -> N. So instead of Cantor's mapping we could as well used bit-interleaving A054238 (Morton code) to pack together A003557(n) and A173557(n), or equally, A000010(n) and A003557(n).
%H A295887 Antti Karttunen, <a href="/A295887/b295887.txt">Table of n, a(n) for n = 1..65537</a>
%H A295887 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PairingFunction.html">Pairing Function</a>
%H A295887 Wikipedia, <a href="https://en.wikipedia.org/wiki/Pairing_function">Pairing Function</a>
%e A295887 The first ten terms of the sequence f(n) = (1/2)*(2 + ((A003557(n) + A173557(n))^2) - A003557(n) - 3*A173557(n)) are 1, 1, 2, 3, 7, 2, 16, 10, 9, 7. When we assign to each newly occurring term the least unused number k so far (starting by giving k=1 for the initial term, this k increases by one for each new distinct term produced by f(n) when n grows), and for each repeated term the same number it was given the previous time (equal to the number it was given for the first time), we obtain 1, 1, 2, 3, 4, 2, 5, 6, 7, 4, the first 10 terms of this sequence. Note how f(10) = 7 gets 4 because when seven occurred for the first time at f(5), it was the 4th distinct new number in that sequence.
%e A295887 This is also true for the sequence A291756 although there the terms are different: 1, 1, 2, 5, 7, 2, 16, 25, 31, 7.
%o A295887 (PARI)
%o A295887 allocatemem(2^30);
%o A295887 up_to = 65537;
%o A295887 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 A295887 write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
%o A295887 A003557(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 2] = max(0,f[i, 2]-1)); factorback(f); };
%o A295887 A173557(n) = my(f=factor(n)[, 1]); prod(k=1, #f, f[k]-1); \\ This function from _Michel Marcus_, Oct 31 2017
%o A295887 Anotsubmitted7(n) = (1/2)*(2 + ((A003557(n)+A173557(n))^2) - A003557(n) - 3*A173557(n));
%o A295887 write_to_bfile(1,rgs_transform(vector(up_to,n,Anotsubmitted7(n))),"b295887.txt");
%Y A295887 Cf. A000010, A003557, A054238, A173557, A291750, A291756, A295300, A295886.
%K A295887 nonn
%O A295887 1,3
%A A295887 _Antti Karttunen_, Dec 03 2017