22
\$\begingroup\$

Intro

Reverse and add is as simple as it sounds, take n and add it to its digits in reverse order. (e.g. 234 + 432 = 666).

If you apply this process repeatedly some numbers will eventually hit a prime number, and some will never reach a prime.

Example

I currently have

11431 rep.

11431 is not prime
11431 + 13411 = 24842 which is not prime
24842 + 24842 = 49684 which is not prime
49684 + 48694 = 98378 which is not prime
98378 + 87389 = 185767 which is prime!

This number hits a prime

In contrast any multiple of 3 will never hit a prime, this is because the all multiples of 3 have a digit sum that is a multiple of 3 and vice versa. Thus reverse and add on a multiple of 3 will always result in a new multiple of 3 and thus never a prime.

Task

Take a positive integer n and determine if repeatedly reversing and adding will ever result in a prime number. Output a truthy or falsy value. Either truthy for reaches a prime and falsy value for does not or the other way around both are acceptable.

Prime numbers will be considered to reach a prime number in zero iterations.

This is so try to make your code as short as possible.

Test Cases

True for reaches a prime false for never reaches a prime

11 -> True
11431 -> True
13201 -> True
13360 -> True
13450 -> True
1019410 -> True
1019510 -> True
22 -> False
1431 -> False
15621 -> False
14641 -> False

Hint

While I was writing this challenge I discovered a cool trick that makes this problem a good deal easier. It is not impossible without this trick and it is not trivial with it either but it does help. I had a lot of fun discovering this so I will leave it in a spoiler below.

Repeated reverse and add will always hit a multiple of 11 in 6 iterations or less. If it does not hit a prime before it hits a multiple of 11 it will never hit a prime.

\$\endgroup\$
  • \$\begingroup\$ I find it more of a mathematical problem than a coding one. I guess code problems have specific rules laid out which are implemented in the code by the answerer; I don't think that's the case with this challenge. \$\endgroup\$ – Arjun Apr 24 '17 at 2:03
  • \$\begingroup\$ @DobbyTheFree-Elf I think the difference between this problem and typical "coding" problems is that often for the latter, the algorithm to be implemented is obvious and it is just a matter of doing it in as little code as possible. This challenge forces you to come up with a algorithm from scratch. Both pose their own unique puzzles but both are ultimately still coding problems. \$\endgroup\$ – Wheat Wizard Apr 24 '17 at 2:16
  • \$\begingroup\$ I agree with that comment of yours, but in my opinion, coming up with such algorithm present in this challenge is more of a job of a mathematician than a programmer. I don't know what others think, but that's at least what I think. So, this has my downvote. \$\endgroup\$ – Arjun Apr 24 '17 at 2:27
  • 1
    \$\begingroup\$ @DobbyTheFree-Elf I hate to break it to you but finding efficient algorithms to solve a problem in a crucial part of being a good programmer. \$\endgroup\$ – Wheat Wizard Apr 24 '17 at 2:46
  • \$\begingroup\$ I agree with that too. But the algorithm for this challenge will have more mathematical value. One will have to find or create proven mathematical theorems to guarantee a correct output with every possible input, which in my opinion what mathematicians do. Common approaches like brute force etc will not work in this case. \$\endgroup\$ – Arjun Apr 24 '17 at 2:56

12 Answers 12

7
\$\begingroup\$

Ruby, 84 79 77 74 bytes

->x{y=1;x+="#{x}".reverse.to_i while(2...x).any?{|z|0==y=x%z}&&x%11>0;y>0}

Try it online!

If I got it right, when we reach a multiple of 11 we can stop (we will only get multiples of 11 after that)

\$\endgroup\$
  • \$\begingroup\$ There is something more powerful we can prove with the information in the spoiler. \$\endgroup\$ – Wheat Wizard Apr 24 '17 at 11:34
3
\$\begingroup\$

Haskell, 65 bytes

f takes an Integer and returns a Bool. True means it reaches a prime.

f n=gcd(product[2..n-1])n<2||gcd 33n<2&&f(n+read(reverse$show n))

Try it online!

Unfortunately the short but inefficient prime test means that the OP's True test cases other than 11 grow too big to finish. But for example 11432 is a True case that does finish.

You can also try this 3 bytes longer one, for which TIO can finish all the True test cases:

f n=and[mod n i>0|i<-[2..n-1]]||gcd 33n<2&&f(n+read(reverse$show n))

Try it online!

Both versions' prime tests break on 1, but it so happens that it gets to a prime (2) anyway.

Otherwise, I noticed about the same thing as G.B. in the spoiler of the Ruby submission:

Once a number grows to even length, the next iteration will be divisible by 11. Once a number is divisible by 11, so will all following iterations.

\$\endgroup\$
  • \$\begingroup\$ @WheatWizard Well it implies that the number of iterations is bounded, with (sorry, no spoiler tags in comments) max 6 steps to check I think (e.g. 100 is maximal). Trying briefly, this doesn't seem to give me a shorter solution, though. Do you mean something more powerful than that? \$\endgroup\$ – Ørjan Johansen Apr 24 '17 at 12:14
  • \$\begingroup\$ No that was it 6 is the maximum \$\endgroup\$ – Wheat Wizard Apr 24 '17 at 13:33
3
\$\begingroup\$

Python 2, 123 110 bytes

Saved 13 bytes thanks to Ørjan Johansen and Wheat Wizard!

n=input()
while 1:
 if all(n%m for m in range(2,n)):print 1;break
 if n%11==0:print 0;break
 n+=int(`n`[::-1])

Returns 1 if it reaches a prime, 0 if it doesn't. Try it online!

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

Python 2, 78 70 69 bytes

f=lambda x:all(x%a for a in range(2,x))or x%11and f(x+int(`x`[::-1]))

Try it online!

Explanation

This program relies on the fact that

Every number that loss forever will reach a multiple of 11 in less than 6 moves

This program is a recursive lambda with circuited logical comparatives. It first checks if n is prime.

all(x%a for a in range(2,x))

If this is true we return true.

If it is false we check if it is a multiple of 11.

x%11

If false we return false otherwise we return the result of f on the next iteration

f(x+int(`x`[::-1]))
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 bytes

ṚḌ$+$6СÆPS

Try it online!

\$\endgroup\$
  • \$\begingroup\$ For the interest of anyone reading this answer, the last S could be a T as well. RD$+$ can also be +RD$$ or RD+<newline>Ç (all trivial modifications) \$\endgroup\$ – HyperNeutrino Apr 28 '17 at 14:15
  • \$\begingroup\$ @HyperNeutrino I chose S because it has less of a chance of showing anything >1. There is no RD, just ṚḌ, and I chose ṚḌ$+$ so that I could organize it better. \$\endgroup\$ – Erik the Outgolfer Apr 28 '17 at 14:17
  • \$\begingroup\$ I was too lazy to put in the dots; I know why you put S; I should have picked that over T, but that's mostly for everyone else's interest. \$\endgroup\$ – HyperNeutrino Apr 28 '17 at 14:50
1
\$\begingroup\$

05AB1E, 14 13 bytes

EDIT: Saved one byte because input is reused if there aren't enough elements on the stack

[Dp#D11Ö#R+]p

Try it online!

Uses the hint in the question

How it works

[              # begin infinite loop
               # implicit input
 D             # duplicate input
  p            # push primality of input
   #           # if prime, break
    D          # duplicate input
     11        # push 11
       Ö       # push input % 11 == 0
        #      # if multiple of 11, break
               # implicit push input
          R    # reverse input
           +   # add both numbers
            ]  # end infinite loop
             p # push primality of result; 1 if prime, 0 if multiple of 11
               # implicit print
\$\endgroup\$
0
\$\begingroup\$

MATLAB, 88 81 bytes

function r=f(n);r=0;for i=1:7 r=r+isprime(n);n=n+str2num(fliplr(num2str(n)));end;
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 73 bytes

Returns 0 or true.

f=n=>{for(d=n;n%--d;);return d<2||n%11&&f(+[...n+''].reverse().join``+n)}

Commented

This is based on the magic-spoiler formula described by Wheat Wizard.

f = n => {              // given n:
  for(d = n; n % --d;); // find the highest divisor d of n
  return                //
    d < 2 ||            // if this divisor is 1, return true (n is prime)
    n % 11 &&           // else: if 11 is a divisor of n, return 0
    f(                  // else: do a recursive call with
      +[...n + '']      // the digits of n
      .reverse().join`` // reversed, joined,
      + n               // coerced to a number and added to n
    )                   //
}                       //

Test cases

I've removed the two largest inputs from the snippet, as they take a few seconds to complete. (But they do work as well.)

f=n=>{for(d=n;n%--d;);return d<2||n%11&&f(+[...n+''].reverse().join``+n)}

console.log(f(11))      // -> True
console.log(f(11431))   // -> True
console.log(f(13201))   // -> True
console.log(f(13360))   // -> True
console.log(f(13450))   // -> True
console.log(f(22))      // -> False
console.log(f(1431))    // -> False
console.log(f(15621))   // -> False
console.log(f(14641))   // -> False

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

Mathematica, 45 bytes

Or@@PrimeQ@NestList[#+IntegerReverse@#&,#,6]&
\$\endgroup\$
0
\$\begingroup\$

Microsoft Sql Server, 826 786* bytes

* I've recalled about the IIF function that was introduced in Microsoft Sql Server 2012

set nocount on
use rextester
go
if object_id('dbo.n','IF')is not null drop function dbo.n
go
create function dbo.n(@ bigint,@f bigint)returns table as return
with a as(select 0 c union all select 0),b as(select 0 c from a,a t),c as(select 0 c from b,b t),
d as(select 0 c from c,c t),e as(select 0 c from d,d t),f as(select 0 c from e,e t),
v as(select top(@f-@+1)0 c from f)select row_number()over(order by(select 0))+@-1 n from v
go
with u as(select cast(a as bigint)a from(values(11),(11431),(13201),(13360),(13450),(1019410),(1019510),(22),(1431),
(15621),(14641))u(a)),v as(select a,a c from u union all select a,c+reverse(str(c,38))from v
where 0=any(select c%n from dbo.n(2,c/2))and c%11>0)select a,iif(0=any(select max(c)%n from dbo.n(2,max(c)/2)),0,1)
from v group by a option(maxrecursion 0)

Check it online

The more neat formatting

SET NOCOUNT ON;
USE rextester;
GO
IF OBJECT_ID('dbo.n', 'IF') IS NOT NULL DROP FUNCTION dbo.n;
GO
CREATE FUNCTION dbo.n(@ BIGINT,@f BIGINT)RETURNS TABLE AS RETURN
  WITH
    a AS(SELECT 0 c UNION ALL SELECT 0),
    b AS(SELECT 0 c FROM a,a t),
    c AS(SELECT 0 c FROM b,b t),
    d AS(SELECT 0 c FROM c,c t),
    e AS(SELECT 0 c FROM d,d t),
    f AS(SELECT 0 c FROM e,e t),
    v AS(SELECT TOP(@f-@+1)0 c FROM f)
    SELECT ROW_NUMBER()OVER(ORDER BY(SELECT 0))+@-1 n FROM v;
GO
WITH u AS(
  SELECT CAST(a AS BIGINT) a
  FROM(VALUES (11), (11431), (13201), (13360), (13450), (1019410), (1019510),
              (22), (1431), (15621), (14641)) u(a)
),
v AS(
  SELECT a, a c FROM u
    UNION ALL
  SELECT a, c + reverse(str(c, 38))
  FROM v
  WHERE 0 = ANY(SELECT c % n FROM dbo.n(2, c / 2)) AND c % 11 > 0
)
SELECT a, IIF(0 = ANY(SELECT MAX(c) % n FROM dbo.n(2, MAX(c) / 2)), 0, 1)
FROM v
GROUP BY a
OPTION (MAXRECURSION 0);
\$\endgroup\$
  • \$\begingroup\$ Do you need the /*true*/ and /*false*/ comments? \$\endgroup\$ – Esolanging Fruit Apr 24 '17 at 19:08
  • \$\begingroup\$ No. It is the comments that used to separate the input data according to results expected. \$\endgroup\$ – Andrei Odegov Apr 25 '17 at 4:15
  • \$\begingroup\$ Can you delete them? \$\endgroup\$ – Esolanging Fruit Apr 25 '17 at 4:16
  • \$\begingroup\$ Yes of course, the comments can be deleted. \$\endgroup\$ – Andrei Odegov Apr 25 '17 at 4:22
  • \$\begingroup\$ You appear to have hard coded the inputs. I'm not too sure, but I think an acceptable input format is selecting them from a table instead \$\endgroup\$ – Jo King Nov 10 '18 at 9:01
0
\$\begingroup\$

Jelly, 9 bytes

ṚḌ+Ɗ6СẒẸ

Try it online!

How it works

ṚḌ+Ɗ6СẒẸ    Monadic main link.
ṚḌ+Ɗ         Monad: Reverse and add to original.
    6С      Repeatedly apply the above 6 times, collecting all iterations
       ẒẸ    Is any of them a prime?
\$\endgroup\$
0
\$\begingroup\$

PHP 114 bytes

<?php function f($n){$n1=strrev((string)$n);$r=$n+(int)$n1;for($i=2;$i<$r;$i++){if($r%$i==0){die('0');}}die('1');}

More readable version:

<?php function f($n)
{
    $n1 = strrev((string)$n);
    $r = $n + (int)$n1;
    for ($i = 2; $i < $r; $i++) {
        if ($r % $i == 0) {
            die('0');
        }
    }
    die('1');
}

f(11431 );

Try it online!

I used this thing for counting bytes.

\$\endgroup\$
  • \$\begingroup\$ Ah okay, it should terminate. I misunderstood the question then. Edited the question to terminate for false-y cases. \$\endgroup\$ – Andrew Nov 10 '18 at 8:53
  • \$\begingroup\$ Now it always returns false unless the first reverse is a prime. You're also not checking the first case, where \$n\$ is a prime. And TIO has a byte counter for you... it even has an auto-formatter for the submission template that you can use \$\endgroup\$ – Jo King Nov 10 '18 at 8:57

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.