24
\$\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\$
  • 1
    \$\begingroup\$ Why do you have to do it in reverse? cQuents doesn't have that mode :( \$\endgroup\$ – Stephen Aug 3 '17 at 15:12
  • 4
    \$\begingroup\$ @StepHen Just for a change of pace; something different than the usual. \$\endgroup\$ – AdmBorkBork Aug 3 '17 at 15:26
  • 9
    \$\begingroup\$ I feel this would be much better as a decision problem. \$\endgroup\$ – Sriotchilism O'Zaic Aug 3 '17 at 16:41
  • 4
    \$\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\$ – Esolanging Fruit Aug 4 '17 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\$
  • \$\begingroup\$ TIO Isn't down for me, maybe it just got back up? \$\endgroup\$ – Conor O'Brien Aug 3 '17 at 17:03
  • 1
    \$\begingroup\$ Fixed as of 2 mins ago :) \$\endgroup\$ – Jonathan Allan Aug 3 '17 at 17:04
  • \$\begingroup\$ Beautiful! That zip(head(), pop()) trick is really cool. :) \$\endgroup\$ – DJMcMayhem Aug 3 '17 at 17:12
  • \$\begingroup\$ In what encoding is that 7 bytes? \$\endgroup\$ – kylefinn Aug 3 '17 at 19:53
  • 1
    \$\begingroup\$ @kylefinn Jelly has its own code-page, click the bytes link in the header to see it. \$\endgroup\$ – Jonathan Allan Aug 3 '17 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\$
  • 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 '17 at 17:32
  • 1
    \$\begingroup\$ Also show x++show(x-1) can be shortened to show=<<[x,x-1]. \$\endgroup\$ – Laikoni Aug 3 '17 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\$ – Sriotchilism O'Zaic Aug 3 '17 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\$
  • \$\begingroup\$ Can you just drop the R and use implicit range? \$\endgroup\$ – nmjcman101 Aug 3 '17 at 15:29
  • \$\begingroup\$ @nmjcman101 I totally did not know that was a thing. Thanks! \$\endgroup\$ – DJMcMayhem Aug 3 '17 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\$
  • \$\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\$ – Erik the Outgolfer Aug 3 '17 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
    \$\begingroup\$ £İp is equivalent to . Also, you could save a byte with #…ḣ instead of £f…N. \$\endgroup\$ – Zgarb Aug 3 '17 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\$
  • \$\begingroup\$ I am golfing this as soon as possible. Suggestions are welcome. \$\endgroup\$ – Mr. Xcoder Aug 3 '17 at 15:23
  • \$\begingroup\$ 87 bytes \$\endgroup\$ – officialaimm Aug 3 '17 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\$
  • 1
    \$\begingroup\$ 11 bytes \$\endgroup\$ – Oliver Aug 3 '17 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 '17 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\$ – ETHproductions Aug 4 '17 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 '17 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\$ – ETHproductions Aug 4 '17 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\$
  • \$\begingroup\$ You beat me by a few seconds, I beat you by a few bytes :P \$\endgroup\$ – Mr. Xcoder Aug 3 '17 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 '17 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\$
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\$
  • \$\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\$ – Conor O'Brien Aug 3 '17 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 '17 at 17:43
  • \$\begingroup\$ You can always specify in your answer how your program should be compiled. \$\endgroup\$ – Conor O'Brien Aug 3 '17 at 17:57
  • \$\begingroup\$ I guess, feels a bit cheap. But I can add an alternative. \$\endgroup\$ – algmyr Aug 3 '17 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\$ – Conor O'Brien Aug 3 '17 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\$
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\$
0
\$\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\$

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.