Простая формула для замены натуральных в A303765 на A004743

[kthxbye]

Если взять натуральные числа и нуль а также задать, что $a(0)=0$ и выбирать каждое следующее число по правилу, описанному в первом комментарии и в секции примеров последовательности A303765, то получим мы, собственно, A303765, то бишь перестановку натуральных чисел и нуля по заданным условиям.

Условия следующие:

Пусть $\operatorname{OR}$ это операция "ИЛИ" применённая побитно к двоичному представлению двух чисел.

Тогда каждый следующий член $a(n)$ мы получаем следующим образом: если существует как минимум одно или более чисел $k_i$, которые не принадлежат подпоследовательности

$$\left\lbrace a(1),a(2),\cdots,a(n-1)\right\rbrace$$

и для которых выполняется условие

$$a(n-1)\operatorname{OR} k_i = a(n-1)$$

то мы присваиваем $a(n)$ такое число $k_i$, для которого A019565$(k_i)$ минимально.

Если же таких чисел $k_i$ не существует, то мы последовательно заполняем вакантные крайние правые нулевые биты в двоичном представлении $n$ единицами. Т.е. мы меняем сначала крайний справа нуль на единицу и проверяем принадлежит ли результат подпоследовательности

$$\left\lbrace a(1),a(2),\cdots,a(n-1)\right\rbrace$$

Если не принадлежит, то присваиваем его $a(n)$. В противном случае меняем следующий крайний справа нуль на единицу, опять-таки проверяем и т.д.

Поработав с результирующей последовательностью A303765 какое-то время, можно укрепиться в идее, что относительно простой формулы для нее нет. Под относительно простой формулой я понимаю формулу, которая включает максимум две различные последовательности, присутствующие в OEIS.

В названии A303765 есть формула использующая две последовательности, однако одна из них использует разложение числа на простые множители, а вторая связана опять-таки с простыми числами и делителями.

Таким образом, формулу с применением пары вышеупомянутых последовательностей я охарактеризовываю как относительно сложную.

Теперь в чем, собственно, суть задачи: если взять за изначальный материал не натуральные числа и нуль, а последовательность A004743, то бишь числа, которые в двоичном представлении $n$ не содержат паттерна $\left\lbrace110\right\rbrace$, то относительно простая формула возможна.

Как было упомянуто выше, она использует максимум две последовательности. Одну я вам даже подскажу - это A007814. Вам остается лишь определить вторую, которая также присутствует в OEIS, и, собственно, указать в какой именно связке эти две последовательности дают искомый результат.

Вот вам также программка на PARI, которая выдает готовую последовательность сложным образом, т.е. по слегка видоизмененным условиям из A303765:

n=9
is(n)=while(n>5, if(bitand(n, 7)==6, return(0)); n>>=1); 1
A006519(n) = (2^valuation(n, 2));
A019565(n) = {my(j, v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))};
A048675(n) = {my(f = factor(n)); sum(k=1, #f~, f[k, 2]*2^primepi(f[k, 1]))/2;};
v=vector(2^n,i,0)
v[1]=1
for(i=2,2^n, s = Set([]); for(m=1, v[i-1], if((bitor(v[i-1], m)==v[i-1]) && is(m) && sum(k=1,i-1,v[k]==m)==0, s = setunion(Set([A019565(m)]), s);)); if(#s>0, w=A048675(vecmin(s)), w=v[i-1]; until(sum(k=1,i-1,v[k]==w)==0 && is(w), w+=A006519(1+w))); v[i]=w)
print(v)

А вот и первые 512 значений (для удобства нужно удалить в ворде символы ^p, буковка латинская):

[1, 3, 2, 7, 4, 5, 15, 8, 9, 11, 10, 31, 16, 17, 19, 18, 23, 20, 21, 63, 32, 33, 
 35, 34, 39, 36, 37, 47, 40, 41, 43, 42, 127, 64, 65, 67, 66, 71, 68, 69, 79, 72 
, 73, 75, 74, 95, 80, 81, 83, 82, 87, 84, 85, 255, 128, 129, 131, 130, 135, 132, 
 133, 143, 136, 137, 139, 138, 159, 144, 145, 147, 146, 151, 148, 149, 191, 160, 
 161, 163, 162, 167, 164, 165, 175, 168, 169, 171, 170, 511, 256, 257, 259, 258, 
 263, 260, 261, 271, 264, 265, 267, 266, 287, 272, 273, 275, 274, 279, 276, 277, 
 319, 288, 289, 291, 290, 295, 292, 293, 303, 296, 297, 299, 298, 383, 320, 321, 
 323, 322, 327, 324, 325, 335, 328, 329, 331, 330, 351, 336, 337, 339, 338, 343, 
 340, 341, 1023, 512, 513, 515, 514, 519, 516, 517, 527, 520, 521, 523, 522, 543 
, 528, 529, 531, 530, 535, 532, 533, 575, 544, 545, 547, 546, 551, 548, 549, 559 
, 552, 553, 555, 554, 639, 576, 577, 579, 578, 583, 580, 581, 591, 584, 585, 587 
, 586, 607, 592, 593, 595, 594, 599, 596, 597, 767, 640, 641, 643, 642, 647, 644 
, 645, 655, 648, 649, 651, 650, 671, 656, 657, 659, 658, 663, 660, 661, 703, 672 
, 673, 675, 674, 679, 676, 677, 687, 680, 681, 683, 682, 2047, 1024, 1025, 1027, 
 1026, 1031, 1028, 1029, 1039, 1032, 1033, 1035, 1034, 1055, 1040, 1041, 1043, 1 
042, 1047, 1044, 1045, 1087, 1056, 1057, 1059, 1058, 1063, 1060, 1061, 1071, 106 
4, 1065, 1067, 1066, 1151, 1088, 1089, 1091, 1090, 1095, 1092, 1093, 1103, 1096, 
 1097, 1099, 1098, 1119, 1104, 1105, 1107, 1106, 1111, 1108, 1109, 1279, 1152, 1 
153, 1155, 1154, 1159, 1156, 1157, 1167, 1160, 1161, 1163, 1162, 1183, 1168, 116 
9, 1171, 1170, 1175, 1172, 1173, 1215, 1184, 1185, 1187, 1186, 1191, 1188, 1189, 
 1199, 1192, 1193, 1195, 1194, 1535, 1280, 1281, 1283, 1282, 1287, 1284, 1285, 1 
295, 1288, 1289, 1291, 1290, 1311, 1296, 1297, 1299, 1298, 1303, 1300, 1301, 134 
3, 1312, 1313, 1315, 1314, 1319, 1316, 1317, 1327, 1320, 1321, 1323, 1322, 1407, 
 1344, 1345, 1347, 1346, 1351, 1348, 1349, 1359, 1352, 1353, 1355, 1354, 1375, 1 
360, 1361, 1363, 1362, 1367, 1364, 1365, 4095, 2048, 2049, 2051, 2050, 2055, 205 
2, 2053, 2063, 2056, 2057, 2059, 2058, 2079, 2064, 2065, 2067, 2066, 2071, 2068, 
 2069, 2111, 2080, 2081, 2083, 2082, 2087, 2084, 2085, 2095, 2088, 2089, 2091, 2 
090, 2175, 2112, 2113, 2115, 2114, 2119, 2116, 2117, 2127, 2120, 2121, 2123, 212 
2, 2143, 2128, 2129, 2131, 2130, 2135, 2132, 2133, 2303, 2176, 2177, 2179, 2178, 
 2183, 2180, 2181, 2191, 2184, 2185, 2187, 2186, 2207, 2192, 2193, 2195, 2194, 2 
199, 2196, 2197, 2239, 2208, 2209, 2211, 2210, 2215, 2212, 2213, 2223, 2216, 221 
7, 2219, 2218, 2559, 2304, 2305, 2307, 2306, 2311, 2308, 2309, 2319, 2312, 2313, 
 2315, 2314, 2335, 2320, 2321, 2323, 2322, 2327, 2324, 2325, 2367, 2336, 2337, 2 
339, 2338, 2343, 2340, 2341, 2351, 2344, 2345, 2347, 2346, 2431, 2368, 2369, 237 
1, 2370, 2375, 2372, 2373, 2383, 2376, 2377, 2379, 2378, 2399]