# Challenge:

The goal of this code-golf is based around the number 8675309...

Your goal is to print out every prime number from 2 to 8675309, starting with the number 2 and then skipping 8 prime numbers, then skipping 6, then skipping 7, etc. In essence, skip a number of primes determined by the next number in the sequence 8675309. Cycling over to 8 once it reaches 9.

# Output:

2
29


(skipped 8 to get to the 10th prime)

59


(skipped 6 to get to the 17th prime)

97


(skipped 7 to get to the 25th prime)

Example: (PHP-like pseudo-code where $prime is an array containing all the prime numbers.) $tn=1;
$c=1;$na=array(8,6,7,5,3,0,9);
l:
output($prime[$tn]);
if ($prime[$tn]>=8675309) {exit(8675309)};
$c+=1; if ($c>=8) {$c=1};$tn+=$na[$c];
goto l;


When I say skip 8 primes, I mean to go from the #1 prime, to the #10 prime (skipping the 8 in between).

Each number must be on a new line.

When you reach the 0 in 8675309, just just print the next prime number without skipping any.

This is so the shortest code (in-bytes) wins.

• so that just gives a fixed output? Commented Dec 17, 2016 at 2:16
• You can use the code from one of the languages used for the list of primes under a million challenge, and just change 1 million to the number you want. Commented Dec 17, 2016 at 2:28
• Your pseudo code still seems to skip one less than described, it increases $c to early, and if we don't hit 8675309 exactly (do we?), it also prints the first number exceeding that value. Commented Dec 17, 2016 at 3:09 • Most challenges have things that need adjusting before they are ready. For future challenge ideas, I find the sandbox very useful for getting feedback before posting. Commented Dec 17, 2016 at 6:12 • The newly added rule: "The last line of output should be 8675209, regardless of whether the sequence lands on it." does not feel right to me at all, IMO it adds nothing to the challenge and is only here to masquerade an error OP has made in the initial calculations. Commented Dec 17, 2016 at 22:04 ## 10 Answers # Mathematica 67 bytes Doesn't hit 8675309 though - not sure of OP's intention on this. Column@FoldList[NextPrime,2,Flatten@Array[{9,7,8,6,4,1,10}&,12937]]  • Would upvote if it didn't use built-ins for prime numbers ... Commented Dec 17, 2016 at 3:28 • this is mathematica we're talking about--we're lucky that there's not a builtin for this – Zwei Commented Dec 17, 2016 at 3:31 # Wonder, 47 bytes P\tk582161P;(_>@(os tk1P;P\dp +1#0P))cyc8675309  Oh geez, this gets slower and slower as time goes on... # Explanation P\tk582161P;  Takes 582161 (amount of primes <= 8675309) items from the infinite primes list P and redeclares result as P. (_>@(...))cyc8675309  Infinitely cycles the digits of 8675309 and performs a takewhile on the resulting list. os tk1P;P\dp +1#0P  Output the first item in P, drop cycle item + 1 elements from P, and redeclare result as P. This operation on P also acts as a truth value for takewhile; if the list is empty / falsy (meaning that we have reached 8675309), then we stop taking from the cycled list. # Faster implementation (for testing) P\tk582161P;(_>@(os tk1P;P\dp +1#0P;#0))cyc8675309  Still really slow, but noticeably faster. # Jelly, 23 29 24 bytes +6 bytes for a temporary patch to fulfil the requirement to print 8675309. -5 bytes moving to a golfier but slower approach to address that. “⁹Ṁ:’©D‘ẋ“2Ṿ’R®ÆR¤ṁḢ€;®Y  Now too slow to run on TryItOnline, but it runs locally in a couple of minutes, producing the numbers shown below with line feeds in-between (# of primes skipped shown below in parentheses): 2, 29, 59, 97, 127, 149, 151, 199, 257, 293, 349, 383, 409, 419, ... (8) (6) (7) (5) (3) (0) (9) (8) (6) (7) (5) (3) (0) ..., 8674537, 8674727, 8674867, 8675003, 8675053, 8675113, 8675137, 8675309 (8) (6) (7) (5) (3) (0) (4)*  * the last is only an effective skip of 4, as it is simply appended to the list. Click here for a version using 3659 instead of 8675309, which has 19 sets of four skips (rather than 12937 sets of 7) and appends 3659 (which is an effective skip of 6). ### How? “⁹Ṁ:’©D‘ẋ“2Ṿ’R®ÆR¤ṁḢ€;®Y - Main link: no arguments “⁹Ṁ:’ - base 250 number: 8675309 © - save in register D - convert to a decimal list: [8, 6, 7, 5, 3, 0, 9] ‘ - increment: [9,7,8,6,4,1,10] “2Ṿ’ - base 250 number: 12937 ẋ - repeat: [9,7,8,6,4,1,10,9,7,8,6,4,1,10, ... ,9,7,8,6,4,1,10] R - range (vectorises) [[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7], ...] ¤ - nilad followed by link(s) as a nilad ® - retrieve value from register: 8675309 ÆR - prime range [2,3,5,7, ... ,8675309] ṁ - mould the primes like the range list: [[2,3,5,7,11,13,17,19,23],[29,31,37,41,43,47,53],...] Ḣ€ - head €ach: [2,29,59,97,127,149,151,199, ..., 8675137] ® - retrieve value from register: 8675309 ; - concatenate: [2,29,59,97,127,149,151,199, ..., 8675137, 8675309] Y - join with line feeds - implicit print  • The program should print 8675309 out at the end, like the pseudo code does. Commented Dec 17, 2016 at 20:09 • @cascading-style OK, I did not realise from the spec that was a requirement (I should have looked at your pseudo code!). I have fixed it up in a naive way for now and will look at the possibility of changing the method at some point to cut this down in size. Commented Dec 18, 2016 at 17:12 # Ruby, 121 bytes Trailing newline at end of file unnecessary and unscored. P=[] (2..8675309).map{|c|s=1;P.map{|p|s*=c%p};P<<c if s!=0} S=[9,7,8,6,4,1,10]*P[-1] while y=P[0] p y P.shift S.shift end  Explanation: P is an array of primes. c is a candidate prime; s is the product of the residues modulo every smaller prime; if any such residue is zero (indicating that c is composite), s becomes (and stays) zero. The prime number generator is slow. It will take a looooong time to run. Testing was done by substituting a P array generated by more efficient means (specifically, short circuit on even division, and it also helps a lot to stop testing at the square root). ## Haskell, 122 bytes This might be what is asked for: s(a:b)=a:s[c|c<-b,cmoda>0] f(a:b)(s:t)=a:f(drop s b)t main=mapM print$takeWhile(<8675310)$f(s[2..])$cycle[8,6,7,5,3,0,9]


I could save a few bytes by precomputing how many number are needed, and replacing takeWhile with take. That would also allow to adapt to any decision about the last number to be output. It has already printed numbers up to 600000 using very few memory in my test, so I think it can go all the way.

• -1 Doesn't work: rextester.com/GPCX98454 Commented Dec 17, 2016 at 4:07
• Might they have a runtime restriction? It works there if you replace 8675310 with 8675, say. And it works for me (compiled, with optimization, didn't try without) in the original form. A faster machine, startet later than the first test, has already reached 1,600,000. Commented Dec 17, 2016 at 4:26
• Getting a stack space overflow. Now trying with a bigger one. Alternatively, can use a more naive prime generator which leads to the same code size. Commented Dec 17, 2016 at 10:18

(p:z)%(x:r)=print p>>(drop x z)%r
p%x=pure()
[n|n<-[2..8675309],all((>0).mod n)[2..n-1]]%cycle[8,6,7,5,3,0,9]


Try it online! (truncated 8675309 to 8675, otherwise it times out on Try it online)

Usage:

*Main> [n|n0).mod n)[2..n-1]]%cycle[8,6,7,5,3,0,9]
2
29
59
97
127
149
151
199
257
293
349
383
409
419
467
541
587
631
661
691
701
769
829
881
941
983
1013
...


# Perl 6,  65 73  67 bytes

$_=8675309;.[0].put for (2..$_).grep(*.is-prime).rotor(1 X+.comb)


( failed to print 8675137 because of missing :partial )

$_=8675309;.[0].put for ^$_ .grep(*.is-prime).rotor((1 X+.comb),:partial)

$_=8675309;.[0].put for ^($_+33) .grep(*.is-prime).rotor(1 X+.comb)


By shifting up the end of the Range, the :partial can be removed.

Try it ( 5 second limit added ) See it finish

Initial example was timed at 52 minutes 41.464 seconds.

## Expanded:

$_ = 8675309; .[0] # get the first value out of inner list .put # print with trailing newline for # for every one of the following ^($_+33)          # the Range ( add 33 so that ｢.rotor｣ doesn't need ｢:partial｣ )
.grep(*.is-prime) # the primes
.rotor(
1 X+ .comb      # (1 X+ (8,6,7,5,3,0,9)) eqv (9,7,8,6,4,1,10)
)


The result from the rotor call is the following sequence

(
(  2   3   5   7  11  13  17  19  23)     #  9 (8)
( 29  31  37  41  43  47  53)             #  7 (6)
( 59  61  67  71  73  79  83  89)         #  8 (7)
( 97 101 103 107 109 113)                 #  6 (5)
(127 131 137 139)                         #  4 (3)
(149)                                     #  1 (0)
(151 157 163 167 173 179 181 191 193 197) # 10 (9)

(199 211 223 227 229 233 239 241 251)     #  9 (8)
(257 263 269 271 277 281 283)             #  7 (6)
(293 307 311 313 317 331 337 347)         #  8 (7)
(349 353 359 367 373 379)                 #  6 (5)
(383 389 397 401)                         #  4 (3)
(409)                                     #  1 (0)
(419 421 431 433 439 443 449 457 461 463) # 10 (9)

...
)

• Nice answer, how long would it take to finish? Commented Dec 17, 2016 at 23:01
• @cascading-style It takes almost 53 minutes to run to completion. Good thing I let it run to completion, as I forgot a :partial adverb on the call to .rotor Commented Dec 18, 2016 at 1:28

# Befunge, 136 bytes

p2>:1>1+:"~"%55p:"~"/45p:*\!v
1+^<+ 1<_:#!v#%+g55@#*"~"g54:_\:!#v_1-\
p00%7+1: ,+64g00.:_^#!***"'(CS":$<^0-"/"g4 >5g#*^#"~"g5< 8675309  Try it online!, but be aware that it's going to time out long before it reaches the end. A compiled version on my local machine completes in under 10 seconds though. Explanation To test for primality we iterate over the range 2 to sqrt(n) and check if n is a multiple of any of those values - if not, it's a prime. This process is complicated by the fact that the iterated value needs to be stored in a temporary "variable", and since Befunge's memory cells are limited in size, that storage has to be split over two cells. To handle the skipped primes, we use a lookup "table" (which you can see on line 5) to keep track of the different ranges that need to be skipped. I'm not going to do a detailed analysis of the code, because there's quite a lot of interleaving code with commands shared across different code paths in order to save space. This makes things rather difficult to follow and I don't think it would be particularly interesting to anyone that wasn't already familiar with Befunge. Sample Output 2 29 59 97 127 149 151 199 ... 8674397 8674537 8674727 8674867 8675003 8675053 8675113 8675137  # Bash (+coreutils), 98, 94 bytes EDITS: • Optimized row filter a bit, -4 bytes Golfed seq 8675309|factor|grep -oP "^.*(?=: \S*$)"|sed 1b\;printf '%d~45b;' {10,17,25,31,35,36,46}d


Test

>seq 8675309|factor|grep -oP "^.*(?=: \S*$)"|sed 1b\;printf '%d~45b;' {10,17,25,31,35,36,46}d| head -25 2 29 59 97 127 149 151 199 257 293 349 383 409 419 467 541 587 631 661 691 701 769 829 881 941  Try It Online! (limited to N<1000, to make it run fast) The full version takes around ~15 seconds to complete on my machine. • I wonder who put "factor" in coreutils. Commented Jan 9, 2017 at 21:04 • @Jasen see unix.stackexchange.com/a/58105/182018 Commented Jan 9, 2017 at 21:10 # Vyxal, 114 bitsv2, 14.25 bytes Þp»¤j⌈»~Þ<$f›ẇvh


Try it Online!

Bitstring:

001010110011101110011001011110011100110101100010101111000100110100100001101101111001000000011010110111001011110100