Every nth prime number up to 8675309

Question

Read this if you're confused.

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 code-golf so the shortest code (in-bytes) wins.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

Haskell, 122 bytes

This might be what is asked for:

s(a:b)=a:s[c|c<-b,c`mod`a>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.

Answer 6

Haskell, 109 bytes

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

Answer 7

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)

 ...
)

Answer 8

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

Answer 9

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.