The first differences of S

are the non-prime numbers of S

We color in yellow the non-prime numbers of the sequence S; the yellow terms are also the absolute first differences of S:

S = 1, 2, 11, 3, 7, 13, 23, 5, 17, 31, 9, 29, 8, 41, 67, 4, 19, 43, 59, 89, 37, 71, 6, 61, 10, 79, 47, 83, 127, 53, 18, 103, 12, 107, 14...

D =  1  9   8  4  6   10  18 12  14  22 20  21 33  26  63 15  24  16  30  52  34  65 56  51  69  32  36  44   74  35  85   91  95   93...

The quantity of yellow terms so far in S is relatively low because:

- we want S to be a permutation of N;

- we want S to be the lexicographically first sequence obeying all constraints;

- we want D to be a permutation of the non-prime numbers.

Douglas McNeil was quick to find:

S = 1, 2, 11, 3, 7, 13, 23, 5, 17, 31, 9, 29, 8, 41, 67, 4, 19, 43, 59, 89, 37, 71, 6, 61, 10, 79, 47, 83, 127, 53, 18, 103, 12, 107, 14, 101, 73, 113, 151, 22, 97, 20, 131, 21, 109, 33, 137, 179, 26, 149, 63, 15, 139, 24, 157, 16, 163, 223, 167, 229, 283, 30, 173, 52, 197, 263, 181, 227, 277, 34, 193, 65, 191, 55, 199, 51, 211, 69, 233, 32, 239, 36, 241, 311, 44, 257, 74, 35, 251, 85, 269, 91, 271, 95, 281, 93, 293, 87, 307, 28, 313, 40, 331, 389, 38, 337, 129, 347, 75, 317, 77, 353, 421, 111, 349, 433, 110, 359, 431, 88, 383, 461, 76, 373, 463, 367, 467, 104, 379, 443, 523, 42, 397, 153, 401, 123, 409, 503, 86, 419, 48, 439, 124, 449, 115, 457, 133, 479, 141, 491, 147, 487, 60, 557, 56, 509, 62, 499, 54, 547, 253, 521, 143, 541, 121, 563, 145, 569, 661, 66, 571, 82, 577, 46, 599, 50, 587, 701, 243, 601, 709, 159, 593, 128, 613, 719, 607, 727, 829, 126, 641, 739, 136, 619, 144, 617, 148, 659, 797, 160, 631, 761, 643, 811, 142, 677, 164, 683, 201, 647, 207, 673, 203, 653, 205, 70, 691, 823, 267, 743, 213, 733, 883, 183, 751, 39, 216, 821, 166, 757, 184, 769, 941, 178, 787, 977, 773, 907, 1061, 809, 180, 859, 1021, 176, 827, 967, 186, 853, 188, 863, 200, 839, 206, 877, 220, 919, 279, 857, 285, 881, 273, 887, 1009, 291, 911, 1063, 58, 929, 1087, 351, 937, 299, 947, 1093, 208, 953, 218, 971, 1153, 983, 272, 997, 242, 991, 1187, 1013, 1129, 240, 1019, 1213, 1423, 276, 1051, 1249, 1451, 68, 1031, 310, 1033, 238, 1039, 84, 1049, 323, 1069, 249, 1091, 1283, 72, 1097, 343, 1103, 295, 78, 1123, 385, 1109, 297, 1151, 1307, 1531, 90, 1117, 1367, 96, 1163, 1399, 100, 1171, 1427, 363, 1181, 275, 1193, 1439, 64, 1201, 80, 1223, 481, 1229, 355, 1217, 244, 1231, 1453, 248, 1237, 278, 1259, 1471, 286, 1279, 1493, 1721, 1277, 94, 1289, 417, 1297, 333, 1291, 371, 1301, 391, 1303, 315, 1319, 325, 1321, 1553, 334, 1381, 1607, 342, 1327, 324, 1361, 346, 1429, 1663, 338, 1373, 350, 1409, 344, 1433, 1693, 340, 1447, 427, 1459, 497, 1481, 501, 1483, 453, 1487, 447, 1489, 437, 1499, 445, 1511, 493, 1543, 1801, 294, 1549, 268, 1579, 1861, 1559, 1789, 378, 1523, 398, 1567, 1831, 2111, 420, 1597, 442, 1583, 418, 1609, 1871, 1571, 1867, 424, 92, 1601, 595, 1619, 505, 1613, 489, 1621, 495, 1637, 531, 1627, 553, 1657, 1931, 549, 1667, 537, 114, 1669, 1973, 458, 1697, 358, 1699, 108, 1723, 550, 1709, 434, 1747, 465, 1733, 485, 1741, 106, 1753, 112, 1777, 2069, 2339, 120, 1759, 2081, 1783, 102, 1787, 703, 1823, 515, 1811, 98, 1847, 603, 1873, 483, 1877, 475, 1879, 473, 1889, 469, 1901, 2207, 511, 1907, 138, 1913, 637, 1949, 471, 130, 1933, 118, 1951, 2239, 168, 1987, 669, 1979, 535, 1993, 513, 1997, 2251, 519, 2011, 482, 1999, 2311, 446, 2003, 440, 2017, 466, 2027, 2293, 2609, 470, 2039, 450, 2053, 448, 2029, 135, 621, 2063, 2347, 132, 2087, 2377, 556, 2083, 2411, 476, 2099, 2417, 530, 2129, 2437, 520, 150, 2089, 700, 2113, 568, 2141, 2467, 712, 2131, 177, 605, 2137, 655, 2143, 591, 2153, 573, 2161, 585, 172, 2179, 2531, 763, 2203, 609, 2213, 190, 2221, 2551, 2237, 204, 2269, 134, 2243, 2579, 154, 2273, 252, 629, 2267, 2621, 679, 162, 2287, 2647, 845, 2281, 651, 2297, 140, 2309, 781, 2341, 667, 2333, 665, 2351, 675, 2357, 663, 2371, 2719, 639, 2381, 633, 2383, 671, 2389, 2753, 657, 2393, 2713, 699, 2399, 2767, 640, 2447, 578, 2423, 572, 2477, 596, 2459, 2833, 608, 2503, 2879, 614, 122, 2441, 2797, 718, 2543, 620, 152, 2473, 1005, 2521, 871, 158, 2549, 736, 2591, 586, 2539, 2927, 638, 2557, 648, 146, 2617, 2999, 885, 2657, 745, 2593, 735, 2633, 753, 2659, 3049, 182, 2663, 170, 2671, 711, 2677, 725, 2683, 755, 2687, 749, 2689, 3061, 196, 2693, 174, 2699, 116, 2711, 889, 2707, 3109, 779, 2729, 194, 2731, 3137, 2741, 3121, 210, 2777, 3163, 1147, 2749, 775, 2801, 198, 2803, 202, 2789, 3181, 1383, 2791, 963, 2819, 721, 2837, 3203, 723, 2843, 795, 2851, 801, 2861, 3271, 955, 2857, 965, 2887, 3299, 726, 2897, 746, 2909, 3313, 3697, 820, 2917, 842, 192, 2939, 1211, 2903, 1025, 2969, 3331, 754, 2953, 760, 2957, 808, 2963, 217, 1045, 2971, 738, 3001, 724, 3019, 3413, 3821, 812, 3023, 3449, 3011, 3433, 3833, 854, 156, 3037, 224, 3041, 1441, 1027, 250, 3079, 1271, 3067, 1067, 236, 3083, 1299, 3089, 1071, 256, 3119, 1064, 3167, 818, 3187, 3617, 4049, 906, 3191, 3607, 4079, 918, 246, 3169, 1375, 3209, 1137, 3221, 1121, 3229, 1143, 3217, 742, 3251, 3739, 748, 3253, 874, 3259, 862, 3257, 973, 3301, 987, 222, 3307, 1205, 3323, 989, 3329, 959, 3319, 981, 3343, 212, 3347, 1185, 3359, 993, 3361, 214, 3371, 3823, 228, 3373, 444, 3389, 1183, 3391, 1195, 3407, 3863, 4327, 872, 3457, 3911, 880, 3461, 3923, 964, 3463, 3943, 958, 3469, 3929, 4423, 920, 3467, 3967, 4441, 3491, 930, 3499, 910, 3517, 4001, 3511, 912, 3527, 4051, 988, 3529, 4007, 1004, 3533, 4073, 3539, 994, 3547, 4057, 3541, 4093, 996, 232, 3557, 4099, 1219, 3571, 1047, 3559, 226, 3581, 4127, 1265, 3583, 985, 3593, 1003, 3613, 1037, 3623, 4129, 1015, 3631, 1083, 234, 3637, 1325, 3671, 1035, 3659, 4157, 1023, 3643, 1059, 3673, 4177, 1065, 3677, 1089, 3691, 260, 3701, 1353, 3709, 4217, 1107, 3733, 4229, 3793, 1020, 3779, 4297, 1032, 3727, 962, 3719, 984, 3767, 980, 3761, 982, 3797, 4357, 1030, 3769, 4283, 1034, 3803, 1040, 3847, 1042, 3851, 1052, 3877, 4409, 3881, 4447, 1062, 3889, 1054, 3907, 1066, 4003, 4547, 3853, 4391, 4903, 1018, 3917, 4481, 3919, 1050, 258, 3947, 1507, 3931, 1255, 3989, 1281, 4013, 1311, 282, 4019, 302, 4027, 4549, 230, 4021, 4591, 1411, 4091, 1145, ...

Many thanks, Douglas!

(and the equivalent sequence where “non-prime” is replaced by “prime” is there)