Cantor's unspeakable numbers

An unspeakable number is a number which is divisible by seven or has seven as one of its digits. A children game is to count skipping unspeakable numbers

1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...


Cantor's version of the game is the sequence defined by recursively filling in the sequence "1 2 3 4 5 6 ( ) 8..." into the gaps ( ) above.

1 2 3 4 5 6 1 8 9 10 11 12 13 2 15 16 3 18 19 20 4 22 23 24 25 26 5 6 29 30 31 32 33 34 1 36 8 38 ...

Print/output at least the first 7^7 numbers of Cantor's unspeakable number game...

While the definition is given recursively, you are not obliged to use recursion in the code.

This is , so the program with the shortest byte count wins!

Note: The sum of numbers in 1 to 7^7 is 203511962727. The last 10 numbers in that range are 823534 823535 221563 108068 823538 823539 823540 823541 823542 221565.

Pastebin dump of first 1000 iterates: http://pastebin.com/Ksiu9Svf

• Please provide the first 7^7 numbers of that sequence such that we can check our solutions. – flawr Nov 27 '16 at 10:20
• Related – Adnan Nov 27 '16 at 10:29
• In case anybody wants to generate some more numbers and compare results: The sum of the first 7^77 numbers in the sequence is 3336402440238885119980169136020683586413168645292341926482898521634332654984279162327502549917668322950744929983987545341421076028 – Niklas B. Nov 28 '16 at 23:46
• Sure, the number of 1's in that sequence is 22977, which means if you pick an element out of the first 7^77 uniformly at random, you have a 2 * 10^-61 chance of it being a 1 – Niklas B. Nov 29 '16 at 8:10
• In case you are interested, here is a graph showing the growth of the number of repeated ones: drive.google.com/file/d/0B71iQwGfNtw5NGladjdOZVhoNkk/… – Niklas B. Nov 29 '16 at 9:41

Pyth, 2523 22 bytes

Thanks to @Maltysen for -2 bytes

.V1=+Y
?}7+PbjbT@Y~hZb


A program that prints an infinite stream.

Try it online! (Output flushed at intervals and times out at 1 min)

How it works

.V1=+Y
?}7+PbjbT@Y~hZb

Z = 0, Y = []    Implicit variable assignment
.V1              Infinite incrementing for loop with variable b, starting at 1:
=+Y            Y = Y +
(newline)          (Implicitly print the result of the following:)
?                   If
}7                  7 is in
Pb                the prime factorisation of b
+                  or
jbT             the digits of b:
@Y            Index into Y at index
Z          Z
~h          (Increment Z)
else:
b      b

• 23 bytes. It works cuz 7 is prime, so divisibility is can be done through checking the prime factorization, which fits in well with the other check – Maltysen Nov 27 '16 at 21:15
• you can post it, the main part of its yours – Maltysen Nov 27 '16 at 21:19
• Congratulation for winning this contest. I also like @Maltysen 's trick! – mschauer Nov 30 '16 at 23:06

Python 2, 777574 70 bytes

Thanks to @MartinEnder for suggesting the limit of 9e5 which enderd up working after a change.
Thanks to @mschauer for suggesting an infinite stream, saving 4 bytes.

def f(n=0):
i=f()
while 1:n+=1;yield next(i)if'7'innor n%7<1else n


This is a generator that yields an infinite stream of the numbers.

• Could you not remove the upper bound entirely? – mschauer Nov 27 '16 at 13:30
• @mschauer Thanks, didn't think of that one. – PurkkaKoodari Nov 27 '16 at 13:57
• if n%7<1or'7'innelse n might be slightly faster (same byte count), since n%7<1 is faster than checking the string, and or is short-circuiting. It's too bad that yield[n,next(i)][n%7<1or'7'inn] won't work. – mbomb007 Nov 29 '16 at 23:03
• @mbomb007 I don't think speed is an issue here, but thanks. :) – PurkkaKoodari Nov 29 '16 at 23:04

Perl, 474641 39 bytes

Saved 5 bytes thanks to @Dada

say$_=$_%7*!/7/?$_:$a[$b++]for@a=1..1e6  Try It Online! TIO Nexus, now with Perl support! This will truncate the output after a certain point, but if you have Perl installed, you can run it locally to produce the full output. The code makes use of a couple of strange quirks of Perl's syntax, so I'll break down how it works below. Code breakdown: say$_=$_%7*!/7/?$_:$a[$b++]for@a=1..1e6
@a=1..1e6 #Assign the range (1..1,000,000) to the array @a
for          #and then loop through this list, with $_ as an alias for the list member. As an alias, modifying$_ modifies @a.
$_%7*!/7/?$_:$a[$b++]             #Ternary operation
$_%7 #Returns the residue modulo 7... *!/7/ #...and multiplies it by the negation of whether or not there exists a 7$_
#Since % and * have the same operator precedence, it must be evaluated in this order
#otherwise we would get (!/7/*$_)%7 instead of ($_%7)*!/7/
?$_ #If the result is non-zero (i.e. truthy), then return$_
:$a[$b++]             #Otherwise, return the $b-th element of @a, and increment$b
$_= #Reassign the result back to$_, modifying @a
say                                     #Prints the result of the assignment, separated by newlines

• say$a[@a]=$_=... to win 2 bytes if I'm not mistaken. – Dada Nov 27 '16 at 22:30
• @Dada actually since that saves me from having to assign to $_, it saves me 5 bytes. Thanks! – Gabriel Benamy Nov 27 '16 at 22:39 • Oh indeed, I just had a quick look and didn't noticed that assignment in the middle.. good job :) – Dada Nov 27 '16 at 22:41 • It is at this moment (and this moment only!) that I have understood the statement "Perl can be quite the write-only language". – haneefmubarak Nov 28 '16 at 4:52 • @Grimy please don't edit others code. If you want to improve an answer add a comment including the improvement or post your own answer. As you probably won't reach the OP by a comment just post your own answer. – ovs Oct 24 '17 at 20:02 PHP, 80 (Wahooka) 57 54 bytes While the idea is from Wahooka. I think my version is different enough to make it an own answer: for(;;)echo$a[]=strpos(++$n,55)<-$n%7?"$n ":$a[+$b++];  Haskell, 67 66 bytes i#x|mod x 7<1||'7'elemshow x=f!!i:(i+1)#(x+1)|y<-x+1=x:i#y f=0#1  f is an infinite list of the numbers. Try it online! f starts a new iteration with 1 and an index which number to pick of 0. Whenever there's a gap we take a new iteration an pick it's ith element and continue the current iteration with i+1. If there's no gap, we take the current number x and go on without increasing i. Edit: -1 byte thanks to @BMO. MATL, 26 25 bytes 9e5:t7\yFYA!7-A*~s:2M(2M  Try it online! with 9e5 replaced by 9e4, so that the maximum running time and output size of the online compiler are not exceeded. How it works This uses iteration instead of recursion. (In fact, MATL doesn't have recursion). An array of numbers from 1 to 9e5 is first generated (this is enough, because 9e5 exceeds 7^7). Then, numbers that are multiples of 7 or have 7 as digit are identified, and replaced by 1, 2, ... The process is iterated until there are no numbers that need to be replaced. 9e5: % Generate array of numbers [1 2 ... 9e5]. This array will become the % output, after some numbers have been replaced  % Do...while t % Duplicate the array of numbers 7\ % Modulo 7. Gives zero for multiples of 7 y % Duplicate the array of numbers FYA! % Matrix of decimal digits, with a column for each number 7- % Subtract 7 to each entry of that matrix A % Array that contains "true" for columns that only contain nonzeros; % that is, for numbers that do not have 7 as digit * % Multiply. This corresponds to a logical "and" of the two conditions. % A zero indicates that the number at that index needs to be replaced ~ % Logical negate. Each "true" corresponds to a number to be replaced s % Sum. This is the amount of numbers to be replaced, say n : % Push array [1 2 ... n] 2M % Push array of logical values again ( % Replace the numbers at the positions indicated by the logical array % by the values [1 2 ... n] 2M % Push n again. This is used as loop condition, so if it is nonzero % the next iteration will be executed. Note that this executes one % too many iterations: the exit condition is that no replacing has % been needed in the current iteration; but then the current iteration % (which will be the last) was not really necessary. This does not % matter; the last iteration is useless but also harmless % End do...while implicitly. Display implicitly  Tcl, 121 Bytes The trivial solution using infinite loop, nothing fancy.. set r 0;set n 0;while {[set r [expr$r+1]]} {if {![expr $r%7]||(7 in[split$r ""])} {puts [set n [expr $n+1]]} {puts$r}}


Ungolfed:

set r 0
set n 0
while {[set r [expr $r+1]]} { if {![expr$r % 7] || (7 in [split $r ""])} { puts [set n [expr$n+1]]
} {
puts $r } }  • You can use incr. And if tcl version >= 8.6, incr assumes the first iteration an increment of a new variable from 0 to 1 if that variable was not set before; so you can get rid of the first two set instructions. – sergiol May 28 '17 at 15:01 • golfed by me — I removed also some non needed white space. – sergiol May 28 '17 at 15:30 • The site where I posted my golfing suggestions for you has lost them, so I made a my new answer – sergiol May 25 '18 at 23:50 PHP, 106 80 bytes Thank you Ismael Miguel for help with the ternary solution and shorter loop code using for instead of while. Could not verify the last parts of the full sequence due to PhpFiddle's 30 second max runtime. Seems to work at least up to 1K based on the sample output provided by the OP. Golf: for($n=1;;$n++)echo$a[]=!(strpos($n,"7")>-1||$n%7==0)?"$n ":array_shift($a)." ";


Original golfed version:

$n=1;while(1){if(!(strpos($n,"7")>-1||$n%7==0)){echo$a[]=$n." ";}else{echo$a[]=array_shift($a)." ";}$n++;}

• for($n=1;;$n++)echo$a[]=!(strpos($n,7)>-1||$n%7==0)?"$n ":array_shift($a)." "; I don't know the byte count, but I'm sure it is a lot lower than 106 bytes. Try it out and see if it works. – Ismael Miguel Nov 27 '16 at 18:36 • Very nice, thanks for the help. The only modification to your code was to put the first 7 in quotations which added two bytes to your 78 byte version. – Wahooka Nov 27 '16 at 19:11 • You can save 3 bytes or so by doing for($n=1;;$n++)echo$a[]=strpos($n,"7")>-1||$n%7==0?array_shift($a)." ":"$n ";. I'm not sure if you can replace $n%7==0 with !$n%7 but it's worth a try. – Ismael Miguel Nov 27 '16 at 20:08
• Keep going -6 : $n=0 is useless, "7" can be 7. – Crypto Nov 28 '16 at 10:43 • why shift? for(;;)echo$a[]=strpos(++$n,55)<-1&&$n%7?"$n ":$a[++$b-1]; (58 byte). ++$b-1 because $a[null] === null – Christoph Nov 28 '16 at 14:13 Julia, 62 bytes x=[];j=0;for i=1:7^7;x=[x;i%7<1||('7' in "$i")?x[j+=1]:i]end;x


Nothing fancy. Uses that the sequence within the gaps is the sequence itself. Makes excessive array copies to save some bytes.

Perl 6,  74 57 54  53 bytes

sub u{my@u;(1..*).map: {if $_%%7||.comb('7') {@u||=u;@u.shift} else {$_}}}

sub u{(1..*).map: {$_%%7||.comb('7')??(@||=u).shift!!$_}}

sub u{map {$_%%7||.comb('7')??(@||=u).shift!!$_},1..*}

sub u{map {$_%%7||.comb(~7)??(@||=u).shift!!$_},1..*}


Try it

Expanded:

sub u{
map             # for each element transform using:

{ # bare block lambda with implicit parameter ｢$_｣$_ %% 7     # if it is divisible by 7
||          # or
.comb(~7)   # contains the number 7 (implicit method call on ｢$_｣) ?? # then ( @ ||= u ) # store a new instance of the Seq into an unnamed state array if it is empty # ( it is only empty the first time it is seen in this Seq instance ) .shift # pull one off of the front !! # else$_          # return the value
},

1 .. *          # infinite range starting at one ( elements to be mapped over )
}


9\*"~"g9+1:+1::p00:<+3$_^#g01$$<v"~":/"~"p9g00%"~"::+1+g9\*"~"+g :#15#+5#g+#0%#17#\-#/!#+\#5:#5_^>%00g1+9p"~"/00g2+9p::7%!10>>p#0  The second version only works with interpreters that have 32-bit memory cells, and thus isn't strictly standard Befunge, but that lets us store larger values in memory without having to split them across cells. "O":0>\#09#:p#-:#1_v<0.< %7::p9g00:+1g9:p00:<+1_^#g01$$<v01! :#15#+5#g+#0%#17#\-#/!#+\#5:#5_^>p#0  In both cases the program runs indefinitely, but the first version will overflow around the 2 million mark, while the second version should get up to the max int value (around 2 billion). You can Try it online, but you'll need to kill the process to prevent it from trying to run forever. Clojure, 130 bytes #(let[R(range(inc %))](rest((reduce(fn[[r s]i](if(or(=(mod i 7)0)((set(str i))\7))[(assoc r i(r s))(inc s)][r s]))[(vec R)0]R)0)))  Basic reduce, keeping track of contents of the result vector and how many values have been skipped. The last 0 takes first element of the reduced [r s], rest drops first element of the 0-indexed result. Perl6, 41 bytes put {($_=++$)%%7|m/7/??@_[$++]!!$_}…1e6  Tcl, 64 bytes while 1 {puts [expr {[incr i]%7&&7ni[split$i ""]?\$i:[incr s]}]}


Try it online!

• nice! much shorter than mine… – hdrz May 26 '18 at 9:36
• This writes "...33 34 7 36 8 38..." instead of "...33 34 1 36 8 38..." – mschauer May 28 '18 at 13:27
• @mschauer: Ok, I will fix it when I have time... – sergiol Jun 5 '18 at 14:38
• @hdrz I tried your solution and it has the same issue mschauer told about! – sergiol Jun 5 '18 at 14:39

JavaScript, 64 bytes

for(f=n=>!/7/.test(m=++n[0])*m%7?m:f(n.t=n.t||[0]);;)alert(f(f))


output=[];index=0;for(f=n=>!/7/.test(m=++n[0])*m%7?m:f(n.t=n.t||[0]);index<100;)output[index++]=f(f);console.log(output.join(','))

• p.s. to compare with the other few (console.log) JavaScript answers, it's 70 bytes – l4m2 May 26 '18 at 13:10

Japt, 25 bytes

[]L³õ@pX%7«/7/tX ?X:UgV°



Generates first 1,000,000 entries of the sequence and prints them. One million is the shortest number over 7**7 == 823543 in Japt.

The trailing newline is significant, as it activates the implicit assignment to U.

Generating the list only takes around a second, but outputting the entire array will likely make your browser hang.

Unpacked & How it works

[]L³õX{UpX%7&&!/7/tX ?X:UgV++

[]                            Assign empty array to U
L³õX{                       Map over 1 to 1,000,000 inclusive...
X%7&&                  If X is not divisible by 7 and
!/7/tX            X does not have a digit 7
?X:UgV++   then X, otherwise the next element already in U
Up                       Push it to the end of U

Implicit print U


Uses the property that the recursive definition can be resolved by looking at the already generated sequence.