# Find the numbers coprime to their decimal digits

Two numbers are coprime if their greatest common divisor is 1.

Given a positive integer N, your task is to compute the first N terms of OEIS A061116, which is the sequence of positive integers higher than 1 that are coprime to all their decimal digits.

Here are the first few terms of the sequence:

11, 13, 17, 19, 21, 23, 27, 29, 31, 37, 41, 43, 47, 49, 51, 53, 57, 59, 61, 67, 71


You can assume that N < 200.

# Test Cases

Input -> Output

1 -> 11
3 -> 11, 13, 17
6 -> 11, 13, 17, 19, 21, 23
25 -> 11, 13, 17, 19, 21, 23, 27, 29, 31, 37, 41, 43, 47, 49, 51, 53, 57, 59, 61, 67, 71, 73, 79, 81, 83


You may output in any decent form (as a list, with a separator or whatever else). You can take input as the String representation of N or as an integer. Standard I/O rules apply.

Default Loopholes apply. This is , so the shortest code in bytes wins!

• Aw. can't this be a 'check if it's part of the sequence' :P
– Okx
Jul 7 '17 at 20:11
• Also, why exclude 1? :| Jul 7 '17 at 20:12
• @Okx That would be kind of trivial. Jul 7 '17 at 20:12
• I need to finish my builtins so I can actually compete in these Jul 7 '17 at 20:13
• @MartinEnder Because it is not in the OEIS sequence... Do you think I should include it? Jul 7 '17 at 20:13

# Plain English853787738594550538 532 bytes

Removed 66 bytes of white space. Removed 49 bytes by using a more generic output type. Removed 144 bytes by abbreviating variable names, and reusing the quotient and the remainder. Removed 44 bytes by abbreviating an interface. Shortened Destroy the number things. to Destroy the L. Removed 6 bytes by changing "some" to "a", and "number" to "count".

Golfed code:

To create a L number things given a c count:
Put 0 in a i count.
Loop.
Add 1 to a n count.
If the i is at least the c, exit.
If the n is g,
append the n to the L;
Repeat.
To decide if a n count is g:
If the n is at most 10, say no.
Put 1 in a m count.
Loop.
If the m is greater than the n, say yes.
Divide the n by the m giving a q quotient and a r remainder.
Divide the q by 10 giving the q and the r.
Get a gcd given the n and the r.
If the gcd is at least 2, say no.
Multiply the m by 10.
Repeat.


Ungolfed code:

Some special numbers are some number things.

To create some special numbers given a count:
Put 0 in another count.
Loop.
If the other count is at least the count, exit.
If the number is coprime with its digits,
Append the number to the special numbers;
Add 1 to the other count.
Repeat.

To decide if a number is coprime with its digits:
If the number is at most 10, say no.
Put 1 in another number.
Loop.
If the other number is greater than the number, say yes.
Divide the number by the other number giving a quotient and a remainder.
Divide the quotient by 10 giving another quotient and another remainder.
Get a gcd given the number and the other remainder.
If the gcd is greater than 1, say no.
Multiply the other number by 10.
Repeat.


"Some number things" are a doubly-linked list of numbers. The calling code has the responsibility to Destroy the special numbers., so I have added the corresponding bytes.

The Plain English IDE is available at github.com/Folds/english. The IDE runs on Windows. It compiles to 32-bit x86 code.

# Jelly, 10, 8 bytes

gQỊẠ
2Ç#


Try it online!

2 bytes saved thanks to @Dennis!

Explanation:

        # Helper link: Is it in the sequence at all?
Ạ    # All of...
g       # The GCDs of A and...
Q      # The unique digits of A
Ị     # Are less than or equal to 1
#
#     # The first *n* truthy results of
2       # Starting at 2

• Jelly is damn slick. Jul 7 '17 at 21:47
• You can golf a byte off with the new(ish) updates: Try it online! Oct 5 '20 at 15:15

# Perl 6, 39 bytes

{(grep {$_ gcd.comb.all==1},2..*)[^$_]}


Try it online!

# Mathematica, 8070 64 bytes

For[t=2;n=#,n>0,t++,Max[t~GCD~IntegerDigits@t]<2&&Print@t&&n--]&


Try it online!

-10 bytes thanx to @MartinEnder
-6 bytes from @JungHwan Min

Saved a total of 6 bytes thanks to @Laikoni and @Ørjan Johansen

(take[x|x<-[2..],and[xgcdread[c]<2|c<-show x]])


Try it online!

• 53 bytes: Try it online! Jul 8 '17 at 7:43
• 51 bytes with @Laikoni 's improvements + an inner list comprehension: Try it online! Jul 8 '17 at 10:13
• Thanks, I don't often think of using ... Jul 8 '17 at 12:10

q n=take n(filter(\x->1==(maximum$map(x%)(d x)))[11,13..]) d 0=[] d x=mod(x)10:(d(xquot10)) x%0=x x%y=y%(xmody)  # Husk, 11 bytes ↑tfȯεΠṠM⌋dN  Try it online! • i. am. speed.... Oct 5 '20 at 15:19 ## JavaScript (ES6), 93 bytes f=(n,k=11,g=(a,b)=>b?g(b,a%b):a)=>n?[...''+k].some(d=>g(k,d)>1)?f(n,k+1):[k,...f(n-1,k+1)]:[]  # PHP, 120 bytes for($n=2;!$r[$argn-1];$t?:$r[]=$n,$n++)for($t=$i=0;~$s=("$n")[$i++];$t|=$d)for($d=$s?:$t|=1;$s%$d|$n%$d--;);print_r(\$r);


Try it online!

# Japt, 10 bytes

Èì ejX}jUB


Try it

# Husk, 14 bytes

↑tfλΛȯεnḊ¹Ḋd)N


Try it online!

## Explanation

↑tfλΛȯεnḊ¹Ḋd)N
fλ        )N filter all natural numbers by the following lambda:
Λȯ     d   map each digit of the natural number, and check if all are truthy:
Ḋ¹Ḋ    divisors of the digit and divisors of the argument
n       set intersection
ε        has length 1? (co primality check)
t             remove the first element
↑              take n items from the sequence(n → input)