cp's OEIS Frontend

A304083 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of A054429.

%I A304083 #16 May 12 2018 14:44:27
%S A304083 0,1,3,2,7,6,4,5,15,14,12,8,13,9,11,10,31,30,28,24,16,29,25,17,27,26,
%T A304083 18,23,22,20,21,63,19,59,58,56,48,32,62,60,52,36,61,57,49,33,55,54,50,
%U A304083 34,51,35,47,46,44,40,45,41,43,42,127,53,37,39,38,126,124,120,112,96,64,125,121,113,97,65,123,122,114,98,66,119,118,116,100,68,117,101
%N A304083 Permutation of nonnegative integers: Minimal subset/superset bitmask transform of A054429.
%C A304083 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) = A054429(n).
%C A304083 Shares with permutations like A003188, A006068, A163252, A300838, A302846, A303763, A303765, A303767, A303773 and A303775 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 A303775 when it is applied to A193231.
%H A304083 Antti Karttunen, <a href="/A304083/b304083.txt">Table of n, a(n) for n = 0..16383</a>
%H A304083 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A304083 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A304083 Derived sequences:
%F A304083 A052330(a(n)) = A304085(n).
%F A304083 A019565(a(n)) = A304087(n).
%F A304083 A000120(a(n)) = A304089(n).
%e A304083 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 A054429(h_i) is minimized, which happens to be at 6 (as A054429(6) = 5, but A054429(7) = 4, and for n >= 8, A054429(n) >= 8), thus a(4) = 7.
%e A304083 After a(4) = 7, "111" in binary, the submasks "1", "10", and "11" (1-3) are already present in sequence, while submasks "100", "101", "110" (4-6) are not present, and because A054429 is minimized on these three at 6, a(5) = 6.
%o A304083 (PARI)
%o A304083 allocatemem(2^30);
%o A304083 default(parisizemax,2^31);
%o A304083 up_to = (2^17)+2;
%o A304083 A054429(n) = ((3<<#binary(n\2))-n-1);
%o A304083 find_minimal_submask_for_A054429(n,m_inverses) = { my(minval=0,minmask=0); for(m=1,n,if((bitor(m,n)==n) && !mapisdefined(m_inverses,m) && (!minval || (A054429(m) < minval)), minval = A054429(m); minmask = m)); (minmask); };
%o A304083 find_minimal_supermask_for_A054429(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 || (A054429(m) < minval)), minval = A054429(m); minmask = m)); (minmask); };
%o A304083 v304083 = vector(up_to);
%o A304083 m304084 = Map();
%o A304083 w=1; for(n=1,up_to,s = Set([]); if((submask = find_minimal_submask_for_A054429(w,m304084)), w = submask, w = find_minimal_supermask_for_A054429(w,m304084)); v304083[n] = w; mapput(m304084,w,n));
%o A304083 A304083(n) = if(!n,n,v304083[n]);
%o A304083 A304084(n) = if(!n,n,mapget(m304084,n));
%Y A304083 Cf. A304084 (inverse).
%Y A304083 Cf. A054429.
%Y A304083 Cf. also A303767, A303775, A304085, A304087, A304088, A304089.
%K A304083 nonn,base
%O A304083 0,3
%A A304083 _Antti Karttunen_, May 06 2018