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
Improve this question
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Why do you have to do it in reverse? cQuents doesn't have that mode :( \$\endgroup\$ Commented Aug 3, 2017 at 15:12
  • 4
    \$\begingroup\$ @StepHen Just for a change of pace; something different than the usual. \$\endgroup\$ Commented Aug 3, 2017 at 15:26
  • 9
    \$\begingroup\$ I feel this would be much better as a decision problem. \$\endgroup\$ Commented 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\$ Commented Aug 4, 2017 at 3:46

25 Answers 25

Reset to default
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
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ TIO Isn't down for me, maybe it just got back up? \$\endgroup\$ Commented Aug 3, 2017 at 17:03
  • 1
    \$\begingroup\$ Fixed as of 2 mins ago :) \$\endgroup\$ Commented Aug 3, 2017 at 17:04
  • \$\begingroup\$ Beautiful! That zip(head(), pop()) trick is really cool. :) \$\endgroup\$ Commented Aug 3, 2017 at 17:12
  • \$\begingroup\$ In what encoding is that 7 bytes? \$\endgroup\$ Commented 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\$ Commented 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!

Improve this answer
\$\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\$ Commented Aug 3, 2017 at 17:32
  • 1
    \$\begingroup\$ Also show x++show(x-1) can be shortened to show=<<[x,x-1]. \$\endgroup\$ Commented 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\$ Commented 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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Can you just drop the R and use implicit range? \$\endgroup\$ Commented Aug 3, 2017 at 15:29
  • \$\begingroup\$ @nmjcman101 I totally did not know that was a thing. Thanks! \$\endgroup\$ Commented 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)
Improve this answer
\$\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\$ Commented 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!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ £İp is equivalent to ṗ. Also, you could save a byte with #…ḣ instead of £f…N. \$\endgroup\$ Commented Aug 3, 2017 at 15:54
5
\$\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
Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 11 bytes \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Aug 4, 2017 at 13: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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I am golfing this as soon as possible. Suggestions are welcome. \$\endgroup\$ Commented Aug 3, 2017 at 15:23
  • \$\begingroup\$ 87 bytes \$\endgroup\$ Commented 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.
Improve this answer
\$\endgroup\$
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 */ }
Improve this answer
\$\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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You beat me by a few seconds, I beat you by a few bytes :P \$\endgroup\$ Commented 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\$ Commented 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 $_.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 30 bytes \$\endgroup\$ Commented 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; }
Improve this answer
\$\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\$ Commented 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\$ Commented Aug 3, 2017 at 17:43
  • \$\begingroup\$ You can always specify in your answer how your program should be compiled. \$\endgroup\$ Commented Aug 3, 2017 at 17:57
  • \$\begingroup\$ I guess, feels a bit cheap. But I can add an alternative. \$\endgroup\$ Commented 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\$ Commented 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!

Improve this answer
\$\endgroup\$
2
\$\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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 77 bytes

Position[Select[Range@#,PrimeQ@FromDigits[Join@@IntegerDigits/@{#,#-1}]&],#]&
Improve this answer
\$\endgroup\$
1
\$\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!

Improve this answer
\$\endgroup\$
1
\$\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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal 3 L, 6 bytes

Ωv&“⌊Ṅ

Try it Online!

1-indexed

Ωv&“⌊Ṅ­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‏​⁢⁠⁡‌­ Ω # ‎⁡filter from the range [0... input] v&“⌊ # ‎⁢concatenate n+1 and convert to integer Ṅ # ‎⁣prime? # ‎⁤L flag gets the length of the top of the stack 💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 6 bytes

'‹Jæ;L

Try it Online!

 L # Number of values ' ; # Between (implicit) 1 and n ‹J # Where n ++ (n-1) æ # Is prime
Improve this answer
\$\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
Improve this answer
\$\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.

Improve this answer
\$\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

Improve this 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
Improve this answer
\$\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)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyt, 15 bytes

2⇹ŘĐĐ⁻Ḷ⁺Ɩᴇ*+⁻ṗƩ

Try it online!

2⇹Ř implicit input; Řangify from 2 to input ĐĐ Đuplicate twice ⁻Ḷ⁺Ɩᴇ Get lowest power of 10 greater than or equal to each element in the list minus 1 * multiply (element-by-element) + add (element-by-element) ⁻ decrement ṗ test for ṗrimality Ʃ Ʃum the list (implicitly cast to integer); implicit print
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.