26
\$\begingroup\$

The Sequence

Everyone knows the only even prime number is 2. Ho-hum. But, there are certain even numbers n where, when concatenated with n-1, they become a prime number.

For starters, 1 isn't in the list, because 10 isn't prime. Similarly with 2 (21), and 3 (32). However, 4 works because 43 is prime, so it's the first number in the sequence a(1) = 4. The next number that works (neither 6 (65) nor 8 (87) work) is 10, because 109 is prime, so a(2) = 10. Then we skip a bunch more until 22, because 2221 is prime, so a(3) = 22. And so on.

Obviously all terms in this sequence are even, because any odd number n when concatenated with n-1 becomes even (like 3 turns into 32), which will never be prime.

This is sequence A054211 on OEIS.

The Challenge

Given an input number n that fits somewhere into this sequence (i.e., n concatenated with n-1 is prime), output its position in this sequence. You can choose either 0- or 1-indexed, but please state which in your submission.

Rules

  • The input and output can be assumed to fit in your language's native integer type.
  • The input and output can be given in any convenient format.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

The below examples are 1-indexed.

n = 4
1

n = 100
11

n = 420
51
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Why do you have to do it in reverse? cQuents doesn't have that mode :( \$\endgroup\$
    – Stephen
    Aug 3, 2017 at 15:12
  • 4
    \$\begingroup\$ @StepHen Just for a change of pace; something different than the usual. \$\endgroup\$ Aug 3, 2017 at 15:26
  • 9
    \$\begingroup\$ I feel this would be much better as a decision problem. \$\endgroup\$
    – Wheat Wizard
    Aug 3, 2017 at 16:41
  • 6
    \$\begingroup\$ Not only is 2 the only prime number divisible by 2, 3 is also the only prime number divisible by 3, and 5 is the only prime number divisible by 5. In general, a prime number n is always the only prime number divisible by n. It's not special - that's just how prime numbers work. \$\endgroup\$ Aug 4, 2017 at 3:46

22 Answers 22

11
\$\begingroup\$

Jelly,  8  7 bytes

ḊżṖVÆPS

A monadic link taking a sequence member and returning its index in the sequence.

Try it online!

How?

ḊżṖVÆPS - Link: number, n
Ḋ       - dequeue (implicit range) = [ 2   , 3   , 4   ,... ,              n         ]
  Ṗ     - pop (implicit range)     = [   1 ,   2 ,   3 ,... ,                  n-1   ]
 ż      - zip                      = [[2,1],[3,2],[4,3],... ,             [n , n-1]  ]
   V    - evaluate as Jelly code   = [ 21  , 32  , 43  ,... ,         int("n"+"n-1") ]
    ÆP  - is prime? (vectorises)   = [  0  ,  0  ,  1  ,... , isPrime(int("n"+"n-1"))]
      S - sum
\$\endgroup\$
5
  • \$\begingroup\$ TIO Isn't down for me, maybe it just got back up? \$\endgroup\$ Aug 3, 2017 at 17:03
  • 1
    \$\begingroup\$ Fixed as of 2 mins ago :) \$\endgroup\$ Aug 3, 2017 at 17:04
  • \$\begingroup\$ Beautiful! That zip(head(), pop()) trick is really cool. :) \$\endgroup\$
    – DJMcMayhem
    Aug 3, 2017 at 17:12
  • \$\begingroup\$ In what encoding is that 7 bytes? \$\endgroup\$
    – kylefinn
    Aug 3, 2017 at 19:53
  • 2
    \$\begingroup\$ @kylefinn Jelly has its own code-page, click the bytes link in the header to see it. \$\endgroup\$ Aug 3, 2017 at 19:54
8
\$\begingroup\$

Haskell, 80 75 70 bytes

5 bytes save thanks to Laikoni

p x=all((>0).mod x)[2..x-1]
g n=sum[1|x<-[4..n],p$read$show=<<[x,x-1]]

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think you can use the shorter prime test p x=all((>0).mod x)[2..x-1] which fails for 1, but this should not matter in this case. \$\endgroup\$
    – Laikoni
    Aug 3, 2017 at 17:32
  • 1
    \$\begingroup\$ Also show x++show(x-1) can be shortened to show=<<[x,x-1]. \$\endgroup\$
    – Laikoni
    Aug 3, 2017 at 17:32
  • \$\begingroup\$ @Laikoni Thanks for the tips! I thought the show could be done in a shorter method but I didn't think of a concat map for some reason. \$\endgroup\$
    – Wheat Wizard
    Aug 3, 2017 at 17:44
6
\$\begingroup\$

Jelly, 12, 10, 8 bytes

;’VÆPµ€S

Try it online!

1-2 bytes saved thanks to @nmjmcman101, and 2 bytes saved thanks to @Dennis!

Explanation:

     µ€   # For N in range(input()):
;         #   Concatenate N with...
 ’        #   N-1
  V       #   And convert that back into an integer
   ÆP     #   Is this number prime?
       S  # Sum that list 
\$\endgroup\$
2
  • \$\begingroup\$ Can you just drop the R and use implicit range? \$\endgroup\$
    – nmjcman101
    Aug 3, 2017 at 15:29
  • \$\begingroup\$ @nmjcman101 I totally did not know that was a thing. Thanks! \$\endgroup\$
    – DJMcMayhem
    Aug 3, 2017 at 15:30
5
\$\begingroup\$

05AB1E, 9 8 7 bytes

Code

ƒNN<«pO

Uses the 05AB1E encoding. Try it online!

Explanation

ƒ          # For N in [0 .. input]..
 NN<«      #   Push n and n-1 concatenated
     p     #   Check for primality
      O    #   Sum the entire stack (which is the number of successes)
\$\endgroup\$
1
  • \$\begingroup\$ Of course this takes advantage of the fact that 05AB1E ignores errors...because I don't think you can check whether '0-1' is prime. \$\endgroup\$ Aug 3, 2017 at 17:28
5
\$\begingroup\$

Husk, 13 11 10 bytes

1-indexed solution:

#ȯṗdS¤+d←ḣ

Try it online!

Ungolfed/Explanation

         ḣ -- in the range [1..N]
#          -- count the number where the following predicate is true
        ←  --   decrement number,
    S  d   --   create lists of digits of number and decremented 
     ¤+    --   concatenate,
   d       --   interpret it as number and
 ȯṗ        --   check if it's a prime number

Thanks @Zgarb for -3 bytes!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ £İp is equivalent to . Also, you could save a byte with #…ḣ instead of £f…N. \$\endgroup\$
    – Zgarb
    Aug 3, 2017 at 15:54
4
\$\begingroup\$

Python 2, 87 bytes

-2 bytes thanks to @officialaimm. 1-indexed.

lambda n:sum(all(z%v for v in range(2,z))for i in range(4,n+1)for z in[int(`i`+`i-1`)])

Test Suite.

\$\endgroup\$
2
  • \$\begingroup\$ I am golfing this as soon as possible. Suggestions are welcome. \$\endgroup\$
    – Mr. Xcoder
    Aug 3, 2017 at 15:23
  • \$\begingroup\$ 87 bytes \$\endgroup\$ Aug 3, 2017 at 15:33
4
\$\begingroup\$

Pyth, 12 bytes

smP_s+`d`tdS

Try it online! or Verify all Test Cases.


How?

smP_s+`d`tdSQ  -> Full Program. Takes input from Standard Input. Q means evaluated input
                  and is implicit at the end.

 m         SQ  -> Map over the Inclusive Range: [1...Q], with the current value d.
    s+`d`td    -> Concatenate: d, the current item and: td, the current item decremented. 
                  Convert to int.
  P_           -> Prime?
s              -> Sum, counts the occurrences of True.
\$\endgroup\$
4
\$\begingroup\$

Japt, 15 14 12 11 9 8 bytes

1-indexed.

ÇsiZÄÃèj

Try it

Ç            :Map each Z in the range [0,input)
 s           :  Convert to string
  i          :    Prepend
   ZÄ        :    Z+1
     Ã       :End map
      è      :Count
       j     :  Primes
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 11 bytes \$\endgroup\$
    – Oliver
    Aug 3, 2017 at 16:59
  • \$\begingroup\$ Gah! Why do I have such a blindspot for Æ and Ç?! Thanks, @Oliver; I'll update when I get back to a computer. \$\endgroup\$
    – Shaggy
    Aug 3, 2017 at 17:09
  • \$\begingroup\$ 2o+X (with trailing space) would work in place of [XXÉ], though if I ever get around to auto-balancing [] brackets your solution will be a byte shorter. (Actually 2, since you could then do õ_ZÉ]¬nÃèj) \$\endgroup\$ Aug 4, 2017 at 1:10
  • \$\begingroup\$ @ETHproductions: These days, the fist thing I do when working with an array is check to see if auto-balancing has been added for []! :D \$\endgroup\$
    – Shaggy
    Aug 4, 2017 at 8:11
  • \$\begingroup\$ For some reason I think semicolons have entirely stopped working as well, so I'll try to fix that. Don't think I'll have a chance until tomorrow afternoon though. \$\endgroup\$ Aug 4, 2017 at 13:54
3
\$\begingroup\$

Röda, 73 bytes

{seq 3,_|slide 2|parseInteger`$_2$_1`|{|i|[1]if seq 2,i-1|[i%_!=0]}_|sum}

Try it online!

1-indexed. It uses the stream to do input and output.

Explanation:

{
seq 3,_| /* Create a stream of numbers from 3 to input */
slide 2| /* Duplicate every number except the first and the last
            to create (n-1,n) pairs */
parseInteger`$_2$_1`| /* Concatenate n and n-1 and convert to integer */
{|i| /* For every i in the stream: */
    [1]if seq 2,i-1|[i%_!=0] /* Push 1 if i is a prime
                                (not divisible by smaller numbers) */
}_|
sum /* Return the sum of numbers in the stream */
}
\$\endgroup\$
2
\$\begingroup\$

Pyth, 14 bytes

lfP_Tms+`d`tdS

Try it online!

Explanation

              Q    # Implicit input
             S     # 1-indexed range
     m             # For d in range [1, Q]...
      s+`d`td      # Concatenate d and d - 1
 fP_T              # Filter on primes
l                  # Return the length of the list
\$\endgroup\$
2
  • \$\begingroup\$ You beat me by a few seconds, I beat you by a few bytes :P \$\endgroup\$
    – Mr. Xcoder
    Aug 3, 2017 at 15:52
  • \$\begingroup\$ @Mr.Xcoder My first version was lfTmP_s+`d`tdS, it's unfortunate that I didn't find your trick by myself at that time :) \$\endgroup\$
    – Jim
    Aug 3, 2017 at 16:14
2
\$\begingroup\$

Perl 6, 45 bytes

{first :k,$_,grep {is-prime $_~.pred},1..∞}

Try it online!

The grep produces the sequence of qualifying numbers, then we look for the key (:k) (ie, the index) of the first number in the list that equals the input parameter $_.

\$\endgroup\$
1
  • \$\begingroup\$ 30 bytes \$\endgroup\$
    – Jo King
    Jan 8, 2019 at 21:10
2
\$\begingroup\$

C, 99 94 bytes

1 indexed. It pains me to write primality tests that are so computationally wasteful, but bytes are bytes after all.

If we allow some really brittle stuff, compiling on my machine without optimizations with GCC 7.1.1 the following 94 bytes works (thanks @Conor O'Brien)

i,c,m,k;f(n){c=i=1;for(;++i<n;c+=m==k){for(k=m=1;m*=10,m<i;);for(m=i*m+i-1;++k<m&&m%k;);}n=c;}

otherwise these much more robust 99 bytes does the job

i,c,m,k;f(n){c=i=1;for(;++i<n;c+=m==k){for(k=m=1;m*=10,m<i;);for(m=i*m+i-1;++k<m&&m%k;);}return c;}

Full program, a bit more readable:

i,c,m,k;
f(n){
    c=i=1;
    for(;++i<n;c+=m==k){
        for(k=m=1;m*=10,m<i;);
        for(m=i*m+i-1;++k<m&&m%k;);
    }
    return c;
}

int main(int argc, char *argv[])
{
    printf("%d\n", f(atoi(argv[1])));
    return 0;
}
\$\endgroup\$
6
  • \$\begingroup\$ Depending on your compiler, you may be able to save some bytes by using n=c; instead of return c;: i,c,m,k;f(n){c=i=1;for(;++i<n;c+=m==k){for(k=m=1;m*=10,m<i;);for(m=i*m+i-1;++k<m&&m%k;);}n=c;} \$\endgroup\$ Aug 3, 2017 at 17:02
  • \$\begingroup\$ I can't say I want to use things that even seems to vary with optimization levels. Using GCC, with no optimization -O0 it works, with other optimization flags it doesn't. Interestingly -O1 -O2 and -O3 it returns 0, with -Os it returns 1, with -Og it returns n-1. \$\endgroup\$
    – algmyr
    Aug 3, 2017 at 17:43
  • \$\begingroup\$ You can always specify in your answer how your program should be compiled. \$\endgroup\$ Aug 3, 2017 at 17:57
  • \$\begingroup\$ I guess, feels a bit cheap. But I can add an alternative. \$\endgroup\$
    – algmyr
    Aug 3, 2017 at 18:06
  • \$\begingroup\$ I understand, but I wouldn't feel to bad about doing that--it's one of the tips for golfing in C \$\endgroup\$ Aug 3, 2017 at 18:09
2
\$\begingroup\$

JavaScript (ES6),  49 48  47 bytes

1-indexed. Limited by the call stack size of your engine.

f=n=>n&&f(n-2)+(p=n=>n%--x?p(n):x<2)(x=n+[--n])

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 77 bytes

Position[Select[Range@#,PrimeQ@FromDigits[Join@@IntegerDigits/@{#,#-1}]&],#]&
\$\endgroup\$
1
\$\begingroup\$

Tidy, 33 bytes

index({n:prime(n.n-1|int)}from N)

Try it online!

Explanation

The basic idea is to create a sequence of the valid numbers then return a curried index function.

index({n:prime(n.n-1|int)}from N)
      {n:                }from       select all numbers `n` from...
                               N     the set of natural numbers, such that:
               n.n-1                     `n` concatenated with `n-1`
                    |int                 ...converted to an integer
         prime(         )                ...is prime
index(                          )    function that returns index of input in that sequence
\$\endgroup\$
0
\$\begingroup\$

QBIC, 25 bytes

[:|p=p-µa*z^_l!a$|+a-1}?p

Explanation

[:|     FOR a = 1 to <n>
p=p-    Decrement p (the counter) by
µ       -1 if the following is prime, or 0 if not
        For the concatenating, we multiply 'a' by 10^LENGTH(a), then add a-1$┘p
        Example 8, len(8) = 1, 8*10^1 = 80, add 8-1=7, isPrime(87) = 0
a*z^_l!a$|+a-1
}       Close the FOR loop - this also terminates the prime-test
?p      Print p, the 0-based index in the sequence.

This uses some pretty involved math-thing with a cast-to-string slapped on for good measure. Making a version hat does solely string-based concatenation is one byte longer:

[:|A=!a$+!a-1$┘p=p-µ!A!}?p
\$\endgroup\$
0
\$\begingroup\$

PHP, 203 bytes

<?php $n=($a=$argv[1]).($a-1);$p=[2];$r=0;for($b=2;$b<=$n;$b++){$x=0;if(!in_array($b,$p)){foreach($p as $v)if(!($x=$b%$v))break;if($x)$p[]=$b;}}for($b=1;$b<=$a;$b++)if(in_array($b.($b-1),$p))$r++;die $r;

Try it online!

Uses a 1-based index for output. TIO link has the readable version of the code.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 42+9 = 51 bytes

Uses the -rprime -n flags. 1-indexed.

Works by counting all numbers equal to or below the input that fulfill the condition (or more technically, all numbers that fulfill the n-1 condition). Since the input is guaranteed to be in the sequence, there's no risk of error from a random input like 7 that doesn't "become prime".

p (?3..$_).count{|i|eval(i.next+i).prime?}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 62 bytes

->g{(1..g).count{|r|(2...x=eval([r,r-1]*'')).none?{|w|x%w<1}}}

Try it online!

1-indexed

\$\endgroup\$
0
\$\begingroup\$

Python 2, 85 bytes

1-indexed

lambda n:sum(all(z%v for v in range(2,z))for i in range(3,n)for z in[int(`i+1`+`i`)])

Test

Improvement to Mr. Xcoder's answer

\$\endgroup\$
0
\$\begingroup\$

Java 8, 108 bytes

n->{for(long r=0,q=1,z,i;;){for(z=new Long(q+""+~-q++),i=2;i<z;z=z%i++<1?0:z);if(z>1)r++;if(q==n)return r;}}

0-indexed

Explanation:

Try it online.

n->{                             // Method with integer parameter and long return-type
  for(long r=0,                  //  Result-long, starting at 0
      q=1,                       //  Loop integer, starting at 1
      z,i;                       //  Temp integers
      ;){                        //  Loop indefinitely
    for(z=new Long(q+""+~-q++),  //   Set z to `q` concatted with `q-1`
        i=2;i<z;z=z%i++<1?0:z);  //   Determine if `z` is a prime,
      if(z>1)                    //   and if it indeed is:
        r++;                     //    Increase the result-long by 1
      if(q==n)                   //   If `q` is now equal to the input integer
        return r;}}              //    Return the result
\$\endgroup\$
0
\$\begingroup\$

Stax, 10 bytes

1- Indexed

Äm▬á┌╕|°φ♦

Run and debug it Explanation

Rxr\{$e|pm|+         #Full program, unpacked, implicit input  (Example (4))
R                    #Create [1 to input] range  (ex [1,2,3,4] )             
 x                   #Copy value from x register (ex (4) )
  r                  #Create [0 to input-1] range (ex [0,1,2,3)
   \                 #Create array pair using the range arrays (ex [[1,0],[2,1],[3,2],[4,3]])
    {    m           #Map block
     $e|p            #To string, eval string (toNum), isPrime (ex [1,0] => "10" => 10 => 0)
          |+         #Sum the array to calculate number of truths (ex [0,0,0,1] => 1)
\$\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.