8
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ so that just gives a fixed output? \$\endgroup\$ – Christian Sievers Dec 17 '16 at 2:16
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – trichoplax Dec 17 '16 at 2:28
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Christian Sievers Dec 17 '16 at 3:09
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – trichoplax Dec 17 '16 at 6:12
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – zeppelin Dec 17 '16 at 22:04
4
\$\begingroup\$

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]]
\$\endgroup\$
  • 1
    \$\begingroup\$ Would upvote if it didn't use built-ins for prime numbers ... \$\endgroup\$ – DepressedDaniel Dec 17 '16 at 3:28
  • 7
    \$\begingroup\$ this is mathematica we're talking about--we're lucky that there's not a builtin for this \$\endgroup\$ – Zwei Dec 17 '16 at 3:31
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ The program should print 8675309 out at the end, like the pseudo code does. \$\endgroup\$ – cascading-style Dec 17 '16 at 20:09
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Jonathan Allan Dec 18 '16 at 17:12
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ -1 Doesn't work: rextester.com/GPCX98454 \$\endgroup\$ – cascading-style Dec 17 '16 at 4:07
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Christian Sievers Dec 17 '16 at 4:26
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Christian Sievers Dec 17 '16 at 10:18
2
\$\begingroup\$

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
...
\$\endgroup\$
2
\$\begingroup\$

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)

 ...
)
\$\endgroup\$
  • \$\begingroup\$ Nice answer, how long would it take to finish? \$\endgroup\$ – cascading-style Dec 17 '16 at 23:01
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Brad Gilbert b2gills Dec 18 '16 at 1:28
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

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.