Singly lossy integers: Concatenated sequences missing a single element

Question

I define the method of combining a sequence to mean that every number in the sequence is concatenated as a string, then that result is made an integer.

[1, 2, 3] -> 123

For every finite sequence of at least 3 consecutive integers, missing exactly one element in the sequence, and this missing element may not be the first or last element in the sequence, output the integer resulting from the combined sequence. I am referring to this as a "singly lossy integer".

[1, 2, 3] -> {1, 3} (missing an element) -> 13

This sequence of singly lossy integers is the union of the following subsequences (partitions?):

The first subsequence {n, n+2} is A032607.

{n, n+2}            -> 13, 24, 35, 46, 57, 68, 79, 810, 911, 1012, ...
{n, n+1, n+3}       -> 124, 235, 346, ...
{n, n+2, n+3}       -> 134, 245, 356, ...
{n, n+1, n+2, n+4}  -> 1235, 2346, 3457, ...
{n, n+1, n+3, n+4}  -> 1245, 2356, 3467, ...
{n, n+2, n+3, n+4}  -> 1345, 2456, 3567, ...
... 
for n ∈ ℕ (integers >= 1)

These integers must be printed in ascending order. The first 25 singly lossy integers are below:

13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, ...

First 7597 Singly Lossy Integers

Ungolfed reference implementations. I made it to be faster, rather than smaller.

• Ideone
• TIO (fastest, higher limits)

Rules:

• Shortest code wins
• You may either (say which one):
  • Print the singly lossy integers forever
  • Given a positive integer n, print or return the first n elements as a list, or a comma- or whitespace- delimited string.
• You should support arbitrarily large integers if your language allows it, especially if you're printing forever.

Inspired by / Related

Note: There is not yet an entry in the OEIS for this sequence.

Another note: I named them the "Singly Lossy Integers" so that there could in turn be "Doubly Lossy Integers", "N-ly Lossy Integers", "(N+1)-ly Lossy Integers", and the "Lossy Integers" (union of all of these).

Answer 1

APL (Dyalog Unicode), 62 bytes^SBCS

Infinite printing full program, 63 bytes

s←⍎' '~⍨⍕
{⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]}⍣≡⊂1 3

Try it online!

This one is pretty fast. Theoretically can be made faster using a min heap, but the challenge is code golf after all.

How it works: the concept

If we denote each item in the sequence as a list of integers ([1,3] for 13, [1,2,4] for 124, and so on), observe that subsequent items can be derived from an existing item x in three ways:

• Add 1 to all numbers in x
• Add 1 to all numbers in x, and then prepend the first element of x
• Append 1 plus the last element of x to x

Therefore, the algorithm is to start with the single known value and infinitely run the following:

• Extract the smallest item and print it
• Derive three larger values from it and add them to the list of next candidate items

How it works: the code

s←⍎' '~⍨⍕  ⍝ Helper function: concat a list of numbers
        ⍕  ⍝   Stringify entire array, which will contain blanks between items
   ' '~⍨   ⍝   Remove blanks
  ⍎        ⍝   Eval
s←         ⍝   Store the function to s

⍝ Main program: print all items in the sequence infinitely
{⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]}⍣≡,⊂1 3
{...}⍣≡⊂1 3  ⍝ Specify starting item and infinite loop
       ⊂1 3  ⍝   singleton array containing [1 3]
{...}⍣≡      ⍝   Pass it to the infinite looping function

⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]  ⍝ Single iteration
       ⍵  ⍝ Sorted candidate items
    a←⊃⍵  ⍝ Take the first element and store to a
⎕←s⊢a     ⍝ Concat and print it

b←1+a  ⍝ Add 1 to all items of a and store to b

t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵  ⍝ Add next candidates
                   1↓⍵  ⍝ Remove the first item (already printed)
   (b,⍨⊃a)(a,⊃⌽b)b,     ⍝ Prepend three candidates:
                 b      ⍝   1+a
          (a,⊃⌽b)       ⍝   append 1+last element of a to a
   (b,⍨⊃a)              ⍝   prepend first element of a to 1+a
t←∪                     ⍝ Uniquify and store to t

t[⍋s¨t]  ⍝ t sorted with the key function s (concat'ed value)

Function returning first n values, 62 bytes

⎕CY'dfns'
⊢↑∘{(⍋⊃¨⊂)⍵{a b c←⍵-1 0⍺⋄⍎dab⍕c↓a↓b~⍨⍳⍺}¨↓3cmat⍵}2+⊢

Try it online!

Slower, but still can handle 100 items in around 5 seconds.

How it works: the concept

This solution uses a systematic way to generate all possible singly lossy integers from the list 1..n. It is equivalent to selecting three members from 1..n:

• Select three distinct integers a < b < c from 1..n.
• Take the inclusive range a..c and discard b.

Original list: 1 2 3 4 5 6 7 8 9
Selection:       ^ ^       ^
                 a b       c
Take a..c:       2 3 4 5 6 7
Discard b:       2   4 5 6 7
Result: 24567

I use dfns.cmat to generate all 3-combinations, generate all singly lossy numbers, sort them and take first n elements. We need length n+2 for the combinations because lower numbers won't give enough number of items.

How it works: the code

⎕CY'dfns'  ⍝ Import dfns library, so that we can use cmat

⍝ Inner function: generate enough singly lossy integers
{(⍋⊃¨⊂)⍵{a b c←⍵-1 0⍺⋄⍎dab⍕c↓a↓b~⍨⍳⍺}¨↓3cmat⍵}  ⍝ Input: 2+n

⍵{...}¨↓3cmat⍵  ⍝ Generate all 3-combinations, and get singly lossy integers
        3cmat⍵  ⍝ 3-combinations of 1..2+n
⍵{   }¨↓        ⍝ Map the inner function to each row of above, with left arg 2+n

a b c←⍵-1 0⍺⋄⍎' '~⍨⍕c↓a↓b~⍨⍳⍺  ⍝ From 3-combination to a singly lossy integer
a b c←⍵-1 0⍺  ⍝ Setup the numbers so that
              ⍝ "remove b, drop first a and last c elements" gives desired value
⍎dab⍕c↓a↓b~⍨⍳⍺  ⍝ Compute the target number
     c↓a↓b~⍨⍳⍺  ⍝ Remove b, drop first a and last c elements from 1..2+n
⍎dab⍕           ⍝ Concat the numbers (dab stands for Delete All Blanks)

(⍋⊃¨⊂)  ⍝ APL idiom for sorting

⊢↑∘{...}2+⊢  ⍝ Outer function; input: n
  ∘{...}2+⊢  ⍝   Pass 2+n to the inner function
⊢↑           ⍝   Take first n elements from the result

---

APL (Dyalog Extended), 49 bytes^SBCS

⊢↑∘{∧⍵{a b c←⍵-1 0⍺⋄⍎⌂dab⍕c↓a↓b~⍨⍳⍺}¨↓3⌂cmat⍵}2+⊢

Try it online!

Simply uses extra built-ins provided in Extended version (dfns library pre-loaded as ⌂ functions, ∧ for ascending sort).

Answer 2

Haskell, 131, 114, 106 bytes

iterate(\n->minimum[x|x<-[read(show=<<filter(/=k)[i..j])::Int|i<-[1..n],j<-[i+2..n],k<-[i+1..j-1]],x>n])13

This is limited by the size of Int, but it can be easily extended by replacing Int with Integer.

Less golfed:

concatInt x = read (concatMap show x) ::Int
allUpToN n = [concatInt $ filter (/=k) [i..j] | i <- [1..n], j <- [i+2..n], k <- [i+1..j-1]]
f n = minimum[x | x <- allUpToN, x > n ]
iterate f 13

8 bytes golfed by @nimi.

Answer 3

Mathematica, 101 bytes

Sort@Flatten@Table[FromDigits[""<>ToString/@(z~Range~x~Delete~y)],{x,3,#},{z,1,x-1},{y,2,x-z}][[1;;#]]&

Yay! For once I have the shortest answer! Party[Hard]

Answer 4

Python 3, 136 127 126 122 bytes

brute force solution, I don't even try n=7000 (it already take 10s for n = 100)

r=range
f=lambda n:sorted(int(''.join(str(i+k)for i in r(1,j)if l-i))for k in r(n)for j in r(4,n)for l in r(2,j-1))[:n]

Explanation

# f=lambda n:sorted( int(''.join(str(i+k) for i in r(1,j)   if l-i)) for k in r(n) for j in r(4,n) for l in r(2,j-1))[:n]
#            ──┬──                        ───────┬───────    ───┬──  ──────┬──────  ──────┬──────  ────────┬──────── ─┬─
#              │                                 │              │          │              │                │          └── selection of the n first numbers
#              │                                 │              │          │              │                └── loop to remove missing element
#              │                                 │              │          │              └── loop for the dimension of the list n to be sure we miss nothing xD
#              │                                 │              │          └── loop on the n in op description 
#              │                                 │              └── Test to remove missing element
#              │                                 └── loop on {n, n+1 ...} in the op description
#              └──── sort the list

Results

>>> f(25)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235]

>>> f(100)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, 1245, 1315, 1345, 1416, 1517, 1618, 1719, 1820, 1921, 2022, 2123, 2224, 2325, 2346, 2356, 2426, 2456, 2527, 2628, 2729, 2830, 2931, 3032, 3133, 3234, 3335, 3436, 3457, 3467, 3537, 3567, 3638, 3739, 3840, 3941, 4042, 4143, 4244, 4345, 4446, 4547, 4568, 4578, 4648, 4678, 4749, 4850, 4951, 5052, 5153, 5254, 5355, 5456, 5557, 5658, 5679, 5689, 5759, 5789, 5860, 5961, 6062, 6163, 6264, 6365, 6466, 6567, 6668, 6769, 6870, 6971, 7072, 7173, 7274, 7375]

Thanks to @mbomb007 and @FricativeMelon for their help

Answer 5

Python 3, 319, 270, 251 bytes

t,h,n,k,q*=range,input(),1,2,
while h>len(q)or n*k<=len(str(q[h])):
 q+=[int("".join([str(c+s)for c in t(k+1)if c-y]))for s in t(10**~-n,10**n)for y in t(1,k)]
 if~-n:n*=k;k+=1
 else:n,k=k+1,2
 while n//k*k-n:k+=1
 n//=k;q.sort()
print(q[:h])

Takes an h as input from STDIN and prints an array of the first h singly-lossy integers. It is very fast as well, taking only a few seconds for h=7000.

Explanation: Note that, if we had infinite time, we could simply iterate over all n,k and for each pair drop each of n+1,n+2,...,n+k-1 (k-1 possibilities), and get all (infinitely many) values from those, then just sort the sequence in ascending order and truncate to h elements. Of course, we cannot actually do that, but if we can reach a point where the first sorted h elements can no longer change by adding the values of any future n,k pairs, we can just truncate then and be done, in finite time. For any n,k pair, it has at least floor(log10(n)+1)*k digits, possibly more. So lets group these pairs by the value c(n,k)=floor(log10(n)+1)*k, where we guarantee that if c(a,b)<c(n,k), we process a,b before n,k. If we have the list sorted, and its last element has d digits, and d<c(n,k) for the next n,k we are going to process, we can stop, since we can no longer get a number with that many or fewer digits, since by our guarantee we should have already processed it then, and therefore no matter which numbers we would end up computing, the first h elements can not change, so we can just return them.

So now we just need the function that guarantees the stated order on c(n,k). For each y obtainable for c(n,k), we must process all (n,k) such that y=c(n,k). Let's say L=floor(log10(n)+1) for some n. Therefore y=L*k must hold. Start with k=2,L=y/2, then do k=3,L=y/3;k=4,L=y/4...k=y,L=1, skipping non-integer values of L. To generate the whole c(n,k) function, start with (1,2) with y=2, and increase y by 1 and start again whenever you get L==1. Now we have an enumeration of pairs (L,k), and it satisfies our condition. However, we need to retrieve all possible n from L, which we do by enumerating all integers with L digits. Then for each of those (n,k) pairs, for each of the k-1 possible dropped elements we must generate the lossy number we get as a result, and add it to our list, which starts empty. Then we sort the list and repeat on the next (L,k) pair, stopping when we have d<c(n,k) as stated before.

Code breakdown (a little outdated):

t=range                     #shortens code
def f(r,n,k):               #helper function
 for s in t(10**~-n,10**n): #for the (L,k) pair, add value of (s,k,y)
  for y in t(1,k):r+=[(int("".join(map(str,[c+s for c in t(k+1)if c!=y]))))]
 if n>1:                    #case where L!=1
  n*=k;k+=1                 #multiply n (which is n'/k from prev iter), inc k
 else:n,k=k+1,2             #reset n and k
 while n//k*k-n:k+=1        #find next proper divisor of n
 return(r,n//k,k)           #divide by that divisor and return
def g(h):                   #main function
 q,a,b=[],1,2               #initial values
 while h>=len(q)or a*b<=len(str(q[h])):(q,a,b)=f(q,a,b);q.sort()
 return q[:h]               #continues until at least h numbers and surpassed current max

Answer 6

05AB1E, 17 bytes

∞ʒ.œD0Å?_*€¥1cP2å

Try it online!

Prints the singly lossy integers forever.