7
\$\begingroup\$

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!

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

Plain English 853 787 738 594 550 538 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;
add 1 to the i.
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.
    Add 1 to a number.
    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.

\$\endgroup\$
6
\$\begingroup\$

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
        #
        # Main link:
  #     # The first *n* truthy results of
 Ç      # The last link
2       # Starting at 2
\$\endgroup\$
  • 3
    \$\begingroup\$ Jelly is damn slick. \$\endgroup\$ – Jonah Jul 7 '17 at 21:47
5
\$\begingroup\$

Perl 6, 39 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Mathematica, 80 70 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

\$\endgroup\$
3
\$\begingroup\$

[Haskell], 64 59 58 57 51 bytes

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

(`take`[x|x<-[2..],and[x`gcd`read[c]<2|c<-show x]])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 53 bytes: Try it online! \$\endgroup\$ – Laikoni Jul 8 '17 at 7:43
  • 1
    \$\begingroup\$ 51 bytes with @Laikoni 's improvements + an inner list comprehension: Try it online! \$\endgroup\$ – Ørjan Johansen Jul 8 '17 at 10:13
  • \$\begingroup\$ Thanks, I don't often think of using `...` \$\endgroup\$ – H.PWiz Jul 8 '17 at 12:10
2
\$\begingroup\$

Haskell, 115 bytes

q n=take n(filter(\x->1==(maximum$map(x%)(d x)))[11,13..])
d 0=[]
d x=mod(x)10:(d(x`quot`10))
x%0=x
x%y=y%(x`mod`y)
\$\endgroup\$
1
\$\begingroup\$

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)]:[]
\$\endgroup\$
1
\$\begingroup\$

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!

\$\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.