Project Euler's "Harshad Numbers"

Question

Project Euler Problem 387 states:

A Harshad or Niven number is a number that is divisible by the sum of its digits. 201 is a Harshad number because it is divisible by 3 (the sum of its digits.) When we truncate the last digit from 201, we get 20, which is a Harshad number. When we truncate the last digit from 20, we get 2, which is also a Harshad number. Let's call a Harshad number that, while recursively truncating the last digit, always results in a Harshad number a right truncatable Harshad number.

Also: 201/3=67 which is prime. Let's call a Harshad number that, when divided by the sum of its digits, results in a prime a strong Harshad number.

Now take the number 2011 which is prime. When we truncate the last digit from it we get 201, a strong Harshad number that is also right truncatable. Let's call such primes strong, right truncatable Harshad primes.

Given a number n, determine the first n strong, right truncatable Harshad primes.

Input: An integer, n, where n<50. (This means your program will need to be somewhat efficient.)

Output: The first n strong, right truncatable Harshad primes, with some form of whitespace in between each value.

Reference Table: The first 20 strong, right truncatable Harshad primes are:
1-10:181 211 271 277 421 457 631 2011 2017 2099
11-20:2473 2477 4021 4027 4073 4079 4231 4813 4817 6037 8011

Shortest code wins. Good luck!

Answer 1

Python 188 bytes

r=range(10)
h=zip(r,r)
w=input()
p=lambda n:all(n%~i for i in range(1,int(n**.5)))%n
while w:
 n,s=h.pop(1)
 for i in r:
    d=s+i;i+=10*n
    if i%d<1:h+=[(i,d)]
    if p(n/s)and p(i):print i;w-=1

This could be made shorter, but my primary concern was efficiency. This code maintains a list of the 'right truncable harshad numbers', as well as the their digital sum, and then uses this list to extend itself by one digit iteratively, allowing only new truncable numbers. I don't see any way to obtain the efficiency required without maintaining such a list. Runtime for n<=50 is less than one second.

A less efficient version, which calculates everthing as it goes (139 bytes, has an acceptable runtime for n<=31):

s=9
w=input()
while w:
 n=s=s+2;x=2;f=0
 while n>9:n/=10;z=sum(map(int,`n`));x-=n%z;f=f or(n/z<3)+n/z
 if(1<<s)%s==(1<<f)%f==x:print s;w-=1

Answer 2

Python, 204

def p(x):
 i=2
 while x%i:i+=1
 return i==x
def h(x):s=sum(map(int,`x`));return[0,x/s][x%s<1]
f=lambda x:x<10or h(x/10)and f(x/10)
n=input()
i=99
while n:
 i+=2
 if f(i)and p(h(i/10))and p(i):print i;n-=1

Answer 3

K, 190

w:{i:0;l:();while[x>#l;if[{$[x>9;$[{&/(h:{a=_a:(d:{x%+/"I"$'$x})x})'{-1_"I"$_[-1]\[$x]}x}q:"I"$-1_$x;$[{(h x)&(p:{(x>1)&&/{x-y*x div y}[_x;2_!_x]})d x}q;$[p x;1;0];0];0];0]}i;l,:i];i+:1];l}

.

k)w 10
181 211 271 277 421 457 631 2011 2017 2099

An easier to read version of the unintelligible one-liner above:

d:{x%+/"I"$'$x}                                     /divide number by sum of digits
h:{a=_a:d x}                                        /test for harshad number
t:{-1_"I"$_[-1]\[$x]}                               /right-truncate a number recursively
r:{&/h't x}                                         /right-truncatable harshad
p:{(x>1)&&/{x-y*x div y}[_x;2_!_x]}                 /isPrime
s:{(h x)&p d x}                                     /strong harshad
m:{$[x>9;$[r q:"I"$-1_$x;$[s q;$[p x;1;0];0];0];0]} /strong right truncatable harshad prime
w:{i:0;l:();while[x>#l;if[m i;l,:i];i+:1];l}        /print the first n harshad srthps

Answer 4

Jelly, 22 bytes

DṖSḍḌƊÐƤP$×Ḍ÷SƊẒ$Ɗ×Ẓµ#

Try it online!

This really should be shorter :/

How it works

DṖSḍḌƊÐƤP$×Ḍ÷SƊẒ$Ɗ×Ẓµ# - Main link. No arguments
         $×      Ɗ× µ# - Read an integer, n, and return the first n integers for which the following three conditions are true:
                   Ẓ   -   1. The integer is prime
DṖSḍḌƊÐƤP              -   2. The integer is a right truncatable Harshad number:
D                      -      Convert to digits
 Ṗ                     -      Remove the last one
     ƊÐƤ               -      Generate the suffixes of the digit list, then, for each:
  S                    -        Take the sum of the suffix
    Ḍ                  -        Convert the suffix back to a number
   ḍ                   -        Does the sum divide the number?
        P              -      Is this true for all the suffixes?
DṖ         Ḍ÷SƊẒ$      -   3. The right truncated integer is a strong Harshad number:
D                      -      Convert to digits
 Ṗ                     -      Remove the last digit
                $      -      Group the previous two commands together:
              Ɗ        -        Group the previous three commands together:
             S         -          Take the sum of the digits
           Ḍ           -          Convert back to an integer
            ÷          -          Divide the integer by the sum
               Ẓ       -        Is this number prime?