Combs and Pharaohs

A friend sent me this lately – I was fascinated…

https://www.youtube.com/shorts/pwW6-YpWUuo

[BTW, is it “Pharaoh” or “Faro” Shuffle?]

As I know that Jean-Paul Delahaye wrote a lot about shuffles, I transferred the video to him.

He replied almost immediately:

>Oui, c’est impressionnant

>Dans un autre genre, j’aime bien aussi celui-là :

https://www.youtube.com/watch?v=XUTSMUFqm7k

This kept me thinking… Could we apply a kind of Pharaoh/Faro Shuffle to integers? Let us see – and push integers into one another alternating their digits.

S = 0, …

We push this 0 between the two teeth of 11 in order to form, say, a prime number (101, here). We have:

S = 0, 11, …

We go on with a(3) = 3 (as we always want to extend S with the smallest integer not yet used and not leading to a contradiction – 131 is a prime number):

S = 0, 11, 3, …

The next term will be 17 as 137 is prime (and 17 the smallest available integer not present in S):

S = 0, 11, 3, 17, …

The next term will be 2 (as 127 is prime), etc.

S = 0, 11, 3, 17, 2, 23, 6, 13, 9, 19, 4, 21, 1, 31, 127, 15, 107, 12, …

I hope the above terms are ok – and guess S is infinite as we have, at each step, a choice for a(n+1); indeed a(n+1) can (must!) be one digit shorter or larger than a(n).

____________________

August 22nd update

Jean-Marc Falcoz was quick to correct, extend and graph S 

S = 0,11,3,17,2,23,6,13,1,21,4,19,7,27,5,33,8,39,103,10,153,20,107,12,131,15,109,16,111,26,113,24,101,30,119,14,123,25,117,29,141,22,127,18,133,31,129,28,121,34,169,36,137,32,167,38,147,35,171,43,157,37,9,41,149,44,159,55,139,46,151,45,163,48,173,42,143,51,187,49,177,52,183,50,161,54,179,47,189,58,181,61,207,40,201,53,197,62,191,57,193,60,203,65,213,56,219,68,237,64,211,66,221,71,261,73,199,67,217,70,247,63,227,69,209,75,223,78,241,81,229,79,267,74,249,77,263,59,231,76,273,80,239,72,257,83,243,86,269,84,251,87,253,97,283,90,233,89,317,95,279,82,291,92,297,91,277,1009,100,1011,106,1003,102,1007,120,1001,104,1017,112,1029,124,1023,115,1059,110,1013,114,1031,108,1037,105,1033,135,1027,144,1021,138,1043,126,1019,116,1047,122,1049,134,1079,146,1061,128,1041,136,1051,150,1039,118,1057,145,1069,132,1073,140,1077,125,1053,158,1083,130,1063,148,1071,164,1137,152,1067,162,1081,142,1143,155,1107,172,1093,154,1087,186,1097,165,1103,180,1099,160,1101,182,1113,166,1141,175,1123,174,1127,156,1091,192,1109,170,1131,205,1111,214,1153,202,1117,168,1121,194,1133,210,1147,222,1151,204,1159,198,1139,195,1157,234,1163,185,1169,200,1089,196,1119,176,1161,178,1149,218,1179,184,1191,212,1173,188,1197,190,1167,215,1187,224,1193,242,1209,232,1171,216,1177,208,1129,225,1181,230,1199,228,1189,244,1219,240,1223,236,1211,260,1229,245,1203,220,1237,235,1201,256,1207,258,1213,246,1273,250,1233,206,1239,248,1221,238,1231,262,1183,255,1217,252,1259,264,1271,270,1247,285,1249,276,1243,259,85,271,94,301,1267,226,1227,265,1257,274,1269,275,1301,254,1251,268,1261,289,1263,266,1241,284,1253,288,1279,304,1297,280,1311,272,1289,296,1307,321,88,303,1291,286,1281,278,1287,290,1277,302,1293,299,98,281,1299,293,1329,292,1303,282,1319,287,93,313,96,311,99,307,1317,305,1323,314,1337,294,1327,300,1309,298,1321,315,1313,312,1283,324,1333,295,1347,308,1353,320,1359,319,1339,322,1341,323,1343,309,1349,318,1331,326,1373,332,1361,327,1351,331,1363,316,1357,325,1377,329,1383,338,1367,339,1379,341,1389,356,1431,334,1369,336,1387,306,1391,330,1399,346,1413,310,1381,333,1403,344,1397,350,1409,335,1371,347,1421,353,1407,328,1411,345,1417,342,1427,357,1423,348,1439,354,1433,363,1447,337,1401,355,1393,340,1441,349,1419,352,1429,364,1461,359,1463,360,1499,369,1451,381,1457,366,1469,362,1479,373,1437,343,1507,367,1449,361,1471,351,1481,368,1443,371,1467,376,1459,384,1477,358,1453,375,1493,365,1473,383,1491,370,1501,372,1519,387,1483,379,1513,378,1559,374,1503,388,1489,390,1487,377,1509,380,1529,389,1517,386,1523,392,1497,385,1521,382,1533,391,1531,396,1511,398,1547,404,1553,401,1563,410,1569,397,1537,400,1557,407,1527,394,1539,409,1549,399,1543,405,1561,414,1571,393,1573,411,1577,402,1597,420,1579,403,1551,412,1599,395,1587,413,1581,406,1593,422,1541,408,1607,417,1567,423,1583,419,1589,425,1617,431,1613,426,1591,429,1609,424,1627,418,1611,415,1633,421,1623,433,1639,435,1643,440,1641,437,1619,416,1637,432,1621,430,1653,436,1659,428,1631,447,1673,441,1601,443,1671,442,1683,427,1647,434,1661,444,1669,448,1629,445,1699,439,1657,438,1691,446,1679,452,1677,457,1603,465,1649,453,1667,467,1703,450,1681,456,1651,459,1663,454,1687,468,1709,473,1689,449,1697,455,1701,460,1719,464,1707,451,1713,469,1711,471,1693,475,1747,477,1757,458,1721,479,1733,462,1727,461,1731,472,1717,478,1753,481,1743,466,1749,470,1739,476,1761,497,1751,489,1723,480,1729,490,1789,483,1769,488,1737,485,1779,502,1741,487,1777,474,1763,486,1781,495,1759,463,1819,492,1771,496,1773,482,1767,491,1787,498,1783,484,1797,493,1801,504,1811,507,1817,500,1793,501,1823,528,1831,505,1791,494,1829,519,1813,511,1821,499,1803,515,1799,509,1833,526,1809,517,1807,508,1837,516,1849,513,1841,503,1839,521,1857,506,1851,518,1827,524,1847,534,1871,512,1863,527,1853,551,1889,530,1859,533,1883,536,1877,510,1867,529,1879,520,1873,514,1843,540,1891,543,1901,525,1897,522,1861,535,1881,541,1911,538,1869,532,1899,539,1917,542,1887,559,1893,544,1909,562,1929,545,1907,549,1903,546,1919,554,1967,566,1913,548,1923,547,1941,523,1953,560,1959,583,1927,531,1969,556,1939,537,1921,550,1957,552,1933,561,1931,558,1943,555,1937,564,1951,580,1981,553,1947,571,1989,563,1961,570,1973,572,1971,557,2003,567,2009,569,2013,568,1977,574,1993,582,1987,577,1983,581,1991,573,2023,565,2049,578,1949,576,1963,579,2021,575,1979,588,2033,591,1999,589,2001,584,2007,586,2011,585,2057,593,1997,597,2029,595,2077,600,2039,587,2027,590,2031,604,2037,601,2019,614,2087,603,2017,592,2047,606,2041,615,2083,640,2059,609,2053,612,2081,594,2051,596,2091,598,2043,605,2097,607,2107,618,2141,621,2071,616,2061,608,2067,602,2111,611,2073,617,2069,627,2063,620,2099,623,2109,610,2101,622,2113,624,2089,613,2119,619,2103,599,2093,629,2127,625,2121,631,2079,635,2133,628,2143,645,2131,636,2117,626,2139,634,2149,642,2123,653,2151,632,2129,641,2157,646,2173,649,2137,639,2189,633,2159,651,2167,630,2153,659,2169,637,2161,643,2179,657,2147,638,2183,648,2197,655,2163,652,2187,667,2203,660,2171,647,2213,656,2181,644,2177,650,2193,658,2191,664,2209,666,2201,662,2207,668,2211,689,2249,654,2219,677,2243,663,2263,679,2221,669,2239,661,2251,676,2217,671,2259,670,2223,674,2303,678,2231,683,2253,685,2293,675,2237,684,2269,687,2227,673,2241,665,2199,680,2247,688,2233,700,2287,681,2267,672,2291,690,2257,693,2329,702,2273,692,2261,695,2283,682,2229,703,2277,697,2301,686,2327,705,2317,709,2281,691,2311,708,2279,719,2289,704,2321,699,2333,728,2297,701,2307,718,2319,694,2347,712,2271,710,2313,698,2339,714,2309,696,2299,721,2331,713,2367,707,2351,711,2357,720,2353,729,2341,724,2323,727,2343,730,2377,733,2359,706,2379,725,2337,715,2373,743,2409,722,2369,716,2391,737,2387,731,2363,744,2423,717,2399,746,2397,734,2403,739,2349,736,2389,741,2407,735,2381,723,2401,745,2427,749,2417,750,2413,726,2371,738,2429,732,2383,766,2419,742,2433,757,2361,751,2449,760,2421,755,2411,752,2393,758,2451,740,2439,761,2447,756,2431,772,2457,748,2469,769,2499,764,2453,774,2437,759,2467,753,2443,762,2441,768,2471,771,2461,765,2473,747,2459,777,2483,767,2493,770,2477,782,2487,781,2479,763,2539,796,2503,754,2463,778,2517,785,2489,776,2501,779,2511,775,2481,773,2507,783,2491,787,2509,786,2519,780,2537,789,2521,784,2523,790,2497,801,2531,791,2541,793,2551,792,2527,795,2513,797,2549,788,2559,799,2529,794,2543,798,2563,802,2569,820,2533,804,2567,809,2577,803,2613,800,2607,805,2581,807,2573,806,2553,808,2547,814,2571,821,2583,811,2587,816,2561,810,2599,813,2617,819,2579,818,2601,815,2591,812,2589,817,2593,826,2631,833,2597,827,2657,831,2609,824,2603,842,2619,836,2633,830,2627,822,2621,839,2643,829,2637,823,2611,832,2629,825,2639,843,2659,828,2557,834,2669,848,2661,847,2649,841,2673,854,2679,844,2641,840,2623,838,2677,852,2647,835,2683,850,2667,845,2721,851,2687,837,2653,864,2671,846,2693,855,2701,862,2691,853,2689,859,2707,865,2743,867,2711,863,2697,857,2681,858,2651,876,2717,861,2663,860,2727,856,2703,871,2709,883,2731,873,2729,849,2749,880,2733,877,2719,870,2737,868,2739,866,2757,874,2713,882,2773,888,2809,885,2699,872,2723,878,2747,894,2761,895,2751,869,2753,879,2789,881,2763,889,2767,898,2811,875,2769,887,2783,890,2759,900,2771,884,2787,886,2779,891,2741,899,2799,905,2801,912,2803,892,2797,906,2807,902,2793,904,2791,897,2819,903,2821,909,2777,908,2813,896,2831,893,2823,914,2781,922,2851,910,2841,913,2833,918,2837,915,2843,924,2827,901,2839,916,2859,925,2847,907,2817,923,2907,917,2867,929,2853,928,2829,931,2889,911,2871,940,2863,927,2861,921,2857,919,2887,933,2869,937,2877,941,2873,936,2879,930,2881,943,2883,947,2849,935,2897,932,2927,920,2919,926,2921,948,2903,938,2961,946,2931,950,2891,942,2917,961,2901,955,2893,934,2899,954,2929,939,2909,959,2913,953,2963,944,2943,949,2967,952,2911,957,2939,951,2941,958,2971,966,2923,973,2949,956,2937,964,3003,970,2953,972,2959,984,2969,962,2957,960,2983,969,2933,963,2951,983,2987,945,2977,976,2979,968,2973,977,2981,971,2993,990,3017,978,3001,975,2989,982,2991,988,3009,965,3011,10011,1028,10013,1016,10001,1025,10019,1005,10007,1035,10009,1032,10033,1014,10027,1000,10021,1002,10037,1004,10059,1042,10003,1008,10031,1010,10017,1034,10041,1006,10077,1015,10023,1048,10071,1040,10047,1012,10039,1062,10043,1026,10049,1038,10051,1018,10089,1030,10069,1036,10029,1045,10159,1044,10061,1022,10107,1054,10053,1046,10133,1092,10057,1024,10087,1020,10063,1068,10073,1058,10091,1050,10067,1070,10127,1086,10139,1064,10101,1055,10103,1104,10093,1090,10099,1056,10079,1074,10081,1078,10111,1075,10113,1052,10083,1060,10137,1082,10151,1085,10163,1080,10097,1094,10173,1066,10117,1065,10177,1114,10131,1072,10143,1076,10179,1084,10161,1102,10153,1110,10109,1095,10121,1088,10191,1106,10193,1112,10169,1118,10149,1105,10189,1128,10187,1145,10227,1096,10129,1108,10123,1135,10167,1124,10181,1164,10157,1136,10119,1156,10141,1140,10183,1122,10147,1098,10171,1174,10201,1170,10213,1126,10231,1134,10217,1142,10221,1144,10203,1130,10197,1120,10207,1125,10211,1158,10247,1115,10209,1154,10223,1172,10199,1148,10233,1166,10253,1155,10249,1116,10243,1132,10237,1162,10251,1168,10239,1175,10257,1205,10277,1176,10259,1194,10229,1152,10261,1165,10267,1185,10241,1184,10269,1180,10291,1195,10273,1182, ...

Merci beaucoup, Jean-Marc !

[Is the Pharaoh/Faro metaphor better than the hereunder combs to explain/illustrate this (new) sequence?

Let me know!-] (Coming soon in an OEIS shop close to you)

I must admit I like the pharaohs!