18
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I added a list of the first ~7600 elements, as well as a reference implementation I just completed in Python. \$\endgroup\$ – mbomb007 Feb 22 '16 at 22:10
  • 2
    \$\begingroup\$ This would be a fun fastest-code challenge. \$\endgroup\$ – Michael Klein Feb 23 '16 at 1:13
  • \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Feb 23 '16 at 4:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Michael Klein Feb 23 '16 at 4:23
3
+50
\$\begingroup\$

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]

\$\endgroup\$
  • 1
    \$\begingroup\$ Is that an actual Mathematica built-in? I wouldn't be surprised. :D \$\endgroup\$ – mbomb007 Feb 23 '16 at 4:17
  • 4
    \$\begingroup\$ No, but that can be corrected with Party[_]:=While[True,Print["PARTY!!!"]]. The argument is ignored because all partying is partying. \$\endgroup\$ – CalculatorFeline Feb 23 '16 at 4:24
  • 1
    \$\begingroup\$ @CatsAreFluffy I disagree. Party[Where] should print Here!, and Party[When] should print Now!, etc. Do not think lightly of partying. \$\endgroup\$ – Sanchises Feb 24 '16 at 15:29
  • \$\begingroup\$ Party[x_]:=Switch[x,Where,"Here!",When,"Now!",How,Pause[1];"...Really?",_,While [True,Print["PARTY!!!"]]] \$\endgroup\$ – CalculatorFeline Feb 24 '16 at 16:44
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is this infinite, or does it take n? \$\endgroup\$ – mbomb007 Feb 18 '16 at 23:13
  • \$\begingroup\$ @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). \$\endgroup\$ – Michael Klein Feb 18 '16 at 23:15
  • \$\begingroup\$ Can you link to an interpreter where I can run this? I pasted it into TryHaskell.org and it didn't work. \$\endgroup\$ – mbomb007 Feb 19 '16 at 21:55
  • \$\begingroup\$ @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. \$\endgroup\$ – Michael Klein Feb 20 '16 at 10:10
  • \$\begingroup\$ Wow, it doesn't get very far before timing out. :D \$\endgroup\$ – mbomb007 Feb 21 '16 at 4:53
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Fricative Melon Feb 25 '16 at 16:40
  • \$\begingroup\$ @FricativeMelon right, i'll removed useless space \$\endgroup\$ – Erwan Feb 25 '16 at 17:23
  • \$\begingroup\$ i!=l+k can also be replaced with l+k-i, which saves a byte. \$\endgroup\$ – Fricative Melon Feb 25 '16 at 17:47
  • \$\begingroup\$ @FricativeMelon i added a small description :) \$\endgroup\$ – Erwan Feb 25 '16 at 17:53
  • \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Feb 25 '16 at 20:39
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Feb 24 '16 at 22:19
  • \$\begingroup\$ 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? \$\endgroup\$ – Fricative Melon Feb 25 '16 at 0:56
  • \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Feb 25 '16 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.