A262283 -id:A262283 - cp's OEIS frontend

A262323 Lexicographically earliest sequence of distinct terms such that the decimal representations of two consecutive terms overlap.

1, 10, 11, 12, 2, 20, 22, 21, 13, 3, 23, 30, 33, 31, 14, 4, 24, 32, 25, 5, 15, 41, 16, 6, 26, 42, 27, 7, 17, 51, 18, 8, 28, 52, 29, 9, 19, 61, 36, 43, 34, 40, 44, 45, 50, 35, 53, 37, 63, 38, 73, 39, 83, 48, 54, 46, 60, 56, 55, 57, 65, 58, 75, 47, 64, 49, 74

Offset: 1

Paul Tek, Sep 19 2015

Two terms are said to overlap:
- if the decimal representation of one term is contained in the decimal representation of the other term (for example, 12 and 2 overlap),
- or if, for some k>0, the first k decimal digits (without leading zero) of one term correspond to the k last decimal digits of the other term (for example, 1017 and 1101 overlap).
This sequence is a permutation of the positive integers, with inverse A262255.
The first overlap involving 1 digit occurs between a(1)=1 and a(2)=10.
The first overlap involving 2 digits occurs between a(108)=100 and a(109)=110.
The first overlap involving 3 digits occurs between a(1039)=1017 and a(1040)=1101.
The first overlap involving 4 digits occurs between a(10584)=10212 and a(10585)=11021.

			The first terms of the sequence are:
+----+---------+
| n  | a(n)    |
+----+---------+
|  1 |  1      |
|  2 |  10     |
|  3 | 11      |
|  4 |  12     |
|  5 |   2     |
|  6 |   20    |
|  7 |  22     |
|  8 |   21    |
|  9 |    13   |
| 10 |     3   |
| 11 |    23   |
| 12 |     30  |
| 13 |    33   |
| 14 |     31  |
| 15 |      14 |
| 16 |       4 |
| 17 |      24 |
| 18 |     32  |
| 19 |      25 |
| 20 |       5 |
+----+---------+

Paul Tek, Table of n, a(n) for n = 1..10000
Paul Tek, PERL program for this sequence
Index entries for sequences that are permutations of the natural numbers

Cf. A076654, A262255, A262283.

Cf. A262367 (fixed points), A262411 (ternary version), A262460 (hexadecimal version).

import Data.List (inits, tails, intersect, delete)
a262323 n = a262323_list !! (n-1)
a262323_list = 1 : f "1" (map show [2..]) where
   f xs zss = g zss where
     g (ys:yss) | null (intersect its $ tail $ inits ys) &&
                  null (intersect tis $ init $ tails ys) = g yss
                | otherwise = (read ys :: Int) : f ys (delete ys zss)
     its = init $ tails xs; tis = tail $ inits xs
-- Reinhard Zumkeller, Sep 21 2015

Perl
```
See Links section.
```

def overlaps(a, b):
  s, t = sorted([str(a), str(b)], key = lambda x: len(x))
  if any(t.startswith(s[i:]) for i in range(len(s))): return True
  return any(t.endswith(s[:i]) for i in range(1, len(s)+1))
def aupto(nn):
  alst, aset = [1], {1}
  for n in range(2, nn+1):
    an = 1
    while True:
      while an in aset: an += 1
      if overlaps(an, alst[-1]): alst.append(an); aset.add(an); break
      an += 1
  return alst
print(aupto(67)) # Michael S. Branicky, Jan 10 2021

A262356 a(1) = 1; for n > 1, let s denote the digit-string of a(n-1) with the first digit omitted. Then a(n) is the smallest number not yet present which starts with s, omitting leading zeros.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 13, 30, 14, 40, 15, 50, 16, 60, 17, 70, 18, 80, 19, 90, 21, 100, 22, 23, 31, 101, 102, 24, 41, 103, 32, 25, 51, 104, 42, 26, 61, 105, 52, 27, 71, 106, 62, 28, 81, 107, 72, 29, 91, 108, 82, 200, 33, 34, 43, 35, 53

Offset: 1

Reinhard Zumkeller, Sep 19 2015

A simplified variation of A262282.
A permutation of the positive integers with inverse A262358;
A262363 and A262371 give the primes and where they occur: A262363(n)=a(A262371(n)).
a(A262393(n)) = A262390(n).
It seems clear that every number will appear, but it would be nice to have a formal proof. - N. J. A. Sloane, Sep 20 2015

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers

Cf. A262283, A262282, A262358 (inverse), A262360 (fixed points), A262374 (binary counterpart), A262363 (primes), A262371, A000030, A262390 (starting with 1), A262393.

import Data.List (isPrefixOf, delete, genericIndex)
import Data.Set (singleton, notMember, insert)
a262356 n = a262356_list !! (n-1)
a262356_list = 1 : f "" (singleton "1") where
   f xs s = (read ys :: Int) : f (dropWhile (== '0') ys') (insert ys s)
     where ys@(_:ys') = head
             [vs | vs <- zss, isPrefixOf xs vs, notMember vs s]
   zss = map show [2..]

a[1] = 1; a[n_] := a[n] = Module[{s, k}, s = Rest[IntegerDigits[a[n - 1]]] //. {(0).., d__} :> {d}; For[k = 2, True, k++, If[FreeQ[Array[a, n - 1], k], If[s == {0}, Return[k], If[IntegerDigits[k][[1 ;; Length[s]]] == s, Return[k]]]]]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* Jean-François Alcover, Mar 12 2019 *)

A262350 a(1) = 2. For n>1, let s denote the binary string of a(n-1) with the leftmost 1 and following consecutive 0's removed. Then a(n) is the smallest prime not yet present whose binary representation begins with s.

Original entry on oeis.org

2, 3, 5, 7, 13, 11, 29, 53, 43, 23, 31, 61, 59, 109, 181, 107, 173, 367, 223, 191, 127, 509, 1013, 4013, 3931, 3767, 13757, 11131, 2939, 1783, 3037, 1979, 3821, 3547, 1499, 1901, 877, 2927, 1759, 1471, 1789, 1531, 2029, 2011, 7901, 60887, 56239, 93887, 28351

Offset: 1

Alois P. Heinz, Sep 18 2015

This sequence is infinite. The number of primes that are not in this sequence is conjectured to be infinite.

Proof of first statement, following a comment from David W. Wilson: It follows from standard results about primes in short intervals (see for example Harman, 1982) that there are infinitely many numbers in any base b starting with any nonzero prefix c. So there are infinitely many primes whose binary expansion begins with s, and so a(n) always exists. - N. J. A. Sloane, Sep 19 2015

			: 10                             ... 2
:   11                           ... 3
:    101                         ... 5
:      111                       ... 7
:       1101                     ... 13
:        1011                    ... 11
:          11101                 ... 29
:           110101               ... 53
:            101011              ... 43
:              10111             ... 23
:                11111           ... 31
:                 111101         ... 61
:                  111011        ... 59
:                   1101101      ... 109
:                    10110101    ... 181
:                      1101011   ... 107
:                       10101101 ... 173

Alois P. Heinz, Table of n, a(n) for n = 1..589
G. Harman, Primes in short intervals, Math. Zeit., 180 (1982), 335-348.

Binary analog of A262283.
Primes whose binary expansion begins with binary expansion of 1, 2, 3, 4, 5, 6, 7: A000040, A080165, A080166, A262286, A262284, A262287, A262285.
Cf. A262365.

b:= proc() true end:
a:= proc(n) option remember; local h, k, ok, p, t;
      if n=1 then p:=2
    else h:= (k-> irem(k, 2^(ilog2(k))))(a(n-1)); p:= h;
         ok:= isprime(p) and b(p);
         for t while not ok do
           for k to 2^t-1 while not ok do p:= h*2^t+k;
             ok:= isprime(p) and b(p)
           od
         od
      fi; b(p):= false; p
    end:
seq(a(n), n=1..70);

A089755 a(1)=11; for n>1, a(n) is the smallest prime not occurring earlier beginning with a(n-1) without its first digit. Single-digit primes are not allowed unless they arise from the previous term as multi-digit number with leading zero(s) (i.e., a(n-1) has 0 as second digit) which are remembered for the subsequent left-truncations.

Original entry on oeis.org

11, 13, 31, 17, 71, 19, 97, 73, 37, 79, 907, 7, 701, 101, 103, 3, 307, 709, 911, 113, 131, 311, 1103, 1031, 313, 137, 373, 733, 331, 317, 173, 739, 397, 971, 719, 191, 919, 193, 937, 379, 797, 977, 773, 7307, 3079, 7901, 9011, 1109, 109, 929, 29, 941, 41, 107, 727, 271, 7103, 1033, 337, 3701, 7013

Offset: 1

Amarnath Murthy, Nov 22 2003

Single-digit numbers are not permitted. However, the sequence is calculated allowing leading zeros. See examples. Uniqueness is still determined by the numerical value: 1013, if it appears, cannot be followed by 013 because 13 is already present. - Franklin T. Adams-Watters, Sep 18 2015
The first digit 2 appears in a(50) = 929 following 109 (since 907, 911, 919 occur earlier), and the first digit 4 appears after a(51) = 29 in a(52) = 941 (because a(39) = 937). The first digit 5 appears in a(199), a 55 digit prime which ends in ...51. The digit 8 appears first in a(230), a 95 digit prime ending in ...81. - M. F. Hasler, Sep 18 2015
As noted by Alois P. Heinz in an email, it appears certain that most primes do not occur in this sequence: "Most primes will never show up, because the net length of terms increases with accelerated rate. There are good reasons for that, but I don't have time to write this up now. But see the numerical evidence." In particular, since the density of primes is zero, there comes a point where it is more likely that two (or more) digits need to be added than that a digit can be removed. From that point, the sequence grows at an ever-increasing rate. - Franklin T. Adams-Watters, Sep 19 2015

			After a(1) = 11, the next term must start with 1. 11 is already present, so 13 is next.
After 13, the next term starts with 3, but it cannot be just 3 as that is a single digit.
After 103, dropping the lead digit leaves 03, and 3 has not occurred before, so that is the next term. As sequences in the OEIS are sequences of numbers, not numerals, this appears in the sequence as 3.
The subsequent term will be the next prime having as first digits the preceding 03 with the initial 0 removed (but not the 3 removed). Thus, it must start with 3, and since 3, 31 and 37 have already occurred, it's 307.

M. F. Hasler, Table of n, a(n) for n = 1..250

Cf. A089756.

See A262282 and A262283 for other versions.

A089755(N,D=-1,u=[],a=11)={my(d); for(n=1,N, print1(a","); D>=0&&setsearch(Set(digits(a)),D)&&return([n,a]);u=setunion(u,[a]);a>9&&isprime(a%=10^d=#Str(a)-1)&&d>1&&!setsearch(u,a)&&next;for(d=1,999,a*=10;forstep(i=1,10^d-1,2,ispseudoprime(a+i)&&a+i>9&&!setsearch(u,a+i)&&(a+=i)&&next(3))));a} \\ If a 2nd argument D is given, then returns [n, a(n)] for the first a(n) having the digit D, if this occurs before the limit N. M. F. Hasler, Sep 18 2015

Edited by Franklin T. Adams-Watters, Sep 18 2015

Definition reworded and data corrected and extended by M. F. Hasler, Sep 18 2015

A262282 a(1)=11. For n>1, let s denote the digit-string of a(n-1) with the first digit omitted. Then a(n) is the smallest prime not yet present which starts with s.

Original entry on oeis.org

11, 13, 3, 2, 5, 7, 17, 71, 19, 97, 73, 31, 101, 103, 37, 79, 907, 701, 107, 709, 911, 113, 131, 311, 1103, 1031, 313, 137, 373, 733, 331, 317, 173, 739, 397, 971, 719, 191, 919, 193, 937, 379, 797, 977, 773, 7307, 307, 727, 271, 7103, 1033, 337, 3701, 7013

Offset: 1

Franklin T. Adams-Watters and N. J. A. Sloane, Sep 18 2015

If a(n-1) has a single digit then a(n) is simply the smallest missing prime.
Leading zeros in s are ignored.
The b-file suggests that there are infinitely many primes that do not appear in the sequence. However, there is no proof at present that any particular prime (23, say) never appears.
Alois P. Heinz points out that this sequence and A262283 eventually merge (see the latter entry for details). - N. J. A. Sloane, Sep 19 2015
A variant without the prime number condition: A262356. - Reinhard Zumkeller, Sep 19 2015

			a(1)=11, so s=1, a(2) is smallest missing prime that starts with 1, so a(2)=13. Then s=3, so a(3)=3. Then s is the empty string, so a(4)=2, and so on.

Alois P. Heinz, Table of n, a(n) for n = 1..705

Suggested by A089755. Cf. A262283.

Cf. A262356.

import Data.List (isPrefixOf, delete)
a262282 n = a262282_list !! (n-1)
a262282_list = 11 : f "1" (map show (delete 11 a000040_list)) where
   f xs pss = (read ys :: Integer) :
              f (dropWhile (== '0') ys') (delete ys pss)
              where ys@(_:ys') = head $ filter (isPrefixOf xs) pss
-- Reinhard Zumkeller, Sep 19 2015

More terms from Alois P. Heinz, Sep 18 2015

cp's OEIS Frontend

A262323 Lexicographically earliest sequence of distinct terms such that the decimal representations of two consecutive terms overlap.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Perl

Python

A262356 a(1) = 1; for n > 1, let s denote the digit-string of a(n-1) with the first digit omitted. Then a(n) is the smallest number not yet present which starts with s, omitting leading zeros.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A262350 a(1) = 2. For n>1, let s denote the binary string of a(n-1) with the leftmost 1 and following consecutive 0's removed. Then a(n) is the smallest prime not yet present whose binary representation begins with s.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A262282 a(1)=11. For n>1, let s denote the digit-string of a(n-1) with the first digit omitted. Then a(n) is the smallest prime not yet present which starts with s.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions