cp's OEIS Frontend

A303775 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of Blue code, A193231.

%I A303775 #18 May 12 2018 14:43:53
%S A303775 0,1,3,2,6,4,5,7,15,14,12,8,13,9,11,10,30,16,17,19,18,23,20,21,31,22,
%T A303775 54,50,48,32,51,49,33,55,53,52,36,60,28,24,29,25,27,26,63,61,57,56,40,
%U A303775 62,58,34,59,35,39,38,46,44,45,37,47,41,43,42,106,64,85,84,80,86,82,66,87,81,65,83,67,91,90,88,72,89,73,95,94,92,68,93,69
%N A303775 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of Blue code, A193231.
%C A303775 In "minimal subset/superset bitmask transform", applicable to any N -> N injection f, we start from a(0) = 0, after which for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i for which f(k_i) is minimized; otherwise, a(n) = that h_i for which f(h_i) is minimized among the infinite set of numbers h_i for which bitand(h_i,a(n-1)) = a(n-1) and that are not yet present in the sequence. In this case f(n) = A193231(n).
%C A303775 Shares with permutations like A003188, A006068, A163252, A300838, A302846, A303763, A303765, A303767, A303773 and A304083 the property that when moving from any a(n) to a(n+1) either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes may occur at the same step. Note that A303767 is obtained when the same transform is applied to A001477, and A304083 when it is applied to A054429.
%H A303775 Antti Karttunen, <a href="/A303775/b303775.txt">Table of n, a(n) for n = 0..16383</a>
%H A303775 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A303775 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A303775 Derived sequences:
%F A303775 A019565(a(n)) = A303778(n).
%F A303775 A000120(a(n)) = A303780(n).
%e A303775 After a(3) = 2, "10" in binary, there are no submasks that wouldn't have been used, so one selects from supermasks h_i = "110" (6), "111" (7), "1010" (10), "1011" (11), "1110" (14), "1111" (15), "10010" (18), "10011" (19), etc. that one for which A193231(h_i) is minimized, which happens to be at 6 (as A193231(6) = 6, but A193231(7) = 7, and for n >= 8, A193231(n) >= 8), thus a(4) = 6.
%e A303775 After a(4) = 6, "110" in binary, the submask "10" (2) is already present in sequence, while submask "100" (4) is only one which is not present, thus 4 is selected to be the value of a(5).
%e A303775 After a(8) = 15, "1111" in binary, none of the submasks "1000" (8), "1001" (9), "1010" (10), "1011" (11), "1100" (12), "1101" (13) or "1110" (14) are present, and as A193231 obtains its minimum value in the range [8 .. 14] at 14 (A193231(14) = 9), we have a(9) = 14.
%o A303775 (PARI)
%o A303775 up_to = (2^18)+2;
%o A303775 A193231(n) = { my(x='x); subst(lift(Mod(1, 2)*subst(Pol(binary(n), x), x, 1+x)), x, 2) }; \\ From A193231
%o A303775 v303775 = vector(up_to);
%o A303775 m303776 = Map();
%o A303775 find_minimal_submask_for_A193231(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,n,if((bitor(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A193231(m) < minval)), minval = A193231(m); minmask = m)); (minmask); };
%o A303775 find_minimal_supermask_for_A193231(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,(1<<(1+#binary(n)))-1,if((bitand(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A193231(m) < minval)), minval = A193231(m); minmask = m)); (minmask); };
%o A303775 w=1; for(n=1,up_to,s = Set([]); if((submask = find_minimal_submask_for_A193231(w,m303776)), w = submask, w = find_minimal_supermask_for_A193231(w,m303776)); v303775[n] = w; mapput(m303776,w,n));
%o A303775 A303775(n) = if(!n,n,v303775[n]);
%o A303775 A303776(n) = if(!n,n,mapget(m303776,n));
%Y A303775 Cf. A303776 (inverse).
%Y A303775 Cf. A193231, A303778, A303779, A303780.
%Y A303775 Cf. also A303767, A304083.
%K A303775 nonn,base
%O A303775 0,3
%A A303775 _Antti Karttunen_, May 05 2018