# Singly lossy integers: Concatenated sequences missing a single element

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.

### 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).

• I added a list of the first ~7600 elements, as well as a reference implementation I just completed in Python. – mbomb007 Feb 22 '16 at 22:10
• This would be a fun fastest-code challenge. – Michael Klein Feb 23 '16 at 1:13
• That it would. Is it acceptable to re-post a challenge but with a different winning criterion? If so, I'd wait a week or more first anyway. – mbomb007 Feb 23 '16 at 4:19
• As far as I know, it should be fine. Might want to pop into chat to ask a mod though, just in case/for tips. – Michael Klein Feb 23 '16 at 4:23

# APL (Dyalog Unicode), 62 bytesSBCS

## 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

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 bytesSBCS

⊢↑∘{∧⍵{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).

# 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. • Is this infinite, or does it take n? – mbomb007 Feb 18 '16 at 23:13 • @mbomb007 With Integer, it will continue until you run out of memory (or patience). It'll continue with Int, but will start giving wrong answers once it overflows (> 2^29-1). – Michael Klein Feb 18 '16 at 23:15 • Can you link to an interpreter where I can run this? I pasted it into TryHaskell.org and it didn't work. – mbomb007 Feb 19 '16 at 21:55 • @mbomb007 Best I've found so far is this, though it needs main=print$ that GHCi does not. GHC.io runs out of memory and TryHaskell.org's feature set is too limited. – Michael Klein Feb 20 '16 at 10:10
• Wow, it doesn't get very far before timing out. :D – mbomb007 Feb 21 '16 at 4:53

# 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]

• Is that an actual Mathematica built-in? I wouldn't be surprised. :D – mbomb007 Feb 23 '16 at 4:17
• No, but that can be corrected with Party[_]:=While[True,Print["PARTY!!!"]]. The argument is ignored because all partying is partying. – CalculatorFeline Feb 23 '16 at 4:24
• @CatsAreFluffy I disagree. Party[Where] should print Here!, and Party[When] should print Now!, etc. Do not think lightly of partying. – Sanchises Feb 24 '16 at 15:29
• Party[x_]:=Switch[x,Where,"Here!",When,"Now!",How,Pause[1];"...Really?",_,While [True,Print["PARTY!!!"]]] – CalculatorFeline Feb 24 '16 at 16:44
• outgolfed[Hard] (by more than 50%) – Adám Jan 28 at 9:43

## Python 3, 136127126 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

• You don't need a space between a ) and the following character, and you can add t=range to the beginning of the program and replace all range function calls with t calls. That should reduce the byte count a lot. – Fricative Melon Feb 25 '16 at 16:40
• @FricativeMelon right, i'll removed useless space – Erwan Feb 25 '16 at 17:23
• i!=l+k can also be replaced with l+k-i, which saves a byte. – Fricative Melon Feb 25 '16 at 17:47
• @FricativeMelon i added a small description :) – Erwan Feb 25 '16 at 17:53
• str(i)for i in r(1+k,j+k)if l+k-i can be replaced with str(i+k)for i in r(1,j)if l-i, saving 4 bytes. – mbomb007 Feb 25 '16 at 20:39

# 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

• I think len(q[h]) should be len(str(q[h])) to support arbitrary integers? Or just say if it only works up to a certain bound, since you're taking a parameter, not printing forever. – mbomb007 Feb 24 '16 at 22:19
• I thought x==repr(x)==str(x) for non-negative integers, and can't find any reference to this not being true. Why do you think this is not true? – Fricative Melon Feb 25 '16 at 0:56
• I know this is not true, because I frequently golf in Python. Example. Anything larger than the integer max value (2**63-1) will have an L on the end if using repr. Note that this entry is probably very far along in the sequence. – mbomb007 Feb 25 '16 at 3:05

# 05AB1E, 17 bytes

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


Try it online!

Prints the singly lossy integers forever.