Numbers divisible by the sum and product of their digits

Question

Take a positive integer X. This number is part of the sequence we are interested in if the sum of all digits of X is a divisor of X, and if the product of all digits of X is a divisor of X.

For example, 135 is such a number because 1 + 3 + 5 = 9 which divides 135 = 9 * 15 and 1 * 3 * 5 = 15 which also divides 135.

This is sequence A038186 in the OEIS.

Your task: given an integer N, output the Nth positive integer with such properties.

Inputs and outputs

• Numbers may be 0-indexed or 1-indexed; please indicate which one your answer use.

• The input may be taken through STDIN, as a function argument, or anything similar.

• The output may be printed to STDOUT, returned from a function, or anything similar.

Test cases

The test cases below are 1-indexed.

Input        Output

1            1
5            5
10           12
20           312
42           6912
50           11313

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

05AB1E, 13 12 bytes

Thanks to Emigna for saving a byte!

µNNSONSP‚ÖP½

Explanation:

µ          ½   # Get the nth number for which the following holds:
  NSO          #   The sum of digits of the current number
     NSP       #   And the products of digits of the current number
 N      ‚ÖP    #   Divides the current number
               # If the nth number has been reached, quit and implicitly print N

Uses the CP-1252 encoding. Try it online!

Answer 2

Pyke, 14 bytes (non-competitive) (1-indexed)

~1IY'sB]im%X)@

Try it here!

My god what a lot of new features.

~1             -   infinite list of natural numbers
  IY'sB]im%X)  -  filter(^, V) - remove if any truthiness
   Y           -      digits(i)
    'sB]       -     [sum(^), product(^)]
        im%    -    map(^, %i)
           X   -   splat(^)
             @ - ^[input]

Of which are non-competitive

• a bugfix in I where it would only check if the first item on the stack was truthy
• digits - return a list of digits in the number
• @ used to get the nth item of an infinite list

Of which were being used for the first time:

• all of the above
• infinite lists

Remove the last 2 bytes to get all of these numbers.

Answer 3

C#, 118 bytes

n=>{int x=0,c=0;for(;;){int s=0,p=1,i=++x;while(i>0){s+=i%10;p*=i%10;i/=10;}if((c+=p>0&&x%s+x%p<1?1:0)==n)return x;}};

Full program with ungolfed function and test cases:

using System;

public class Program
{
    public static void Main()
    {
        // x - output number
        // c - counter
        // s - sum
        // p - product
        // i - iterator
        Func<int,int>f= n=>
        {
            int x=0, c=0;
            for ( ; ; )
            {
                int s=0, p=1, i=++x;
                while (i > 0)
                {
                    s += i%10;
                    p *= i%10;
                    i /= 10;
                }
                if ( (c += p> 0&& x%s+x%p<1 ? 1 : 0) == n)
                    return x;
            }
        };

        // tests:
        Console.WriteLine(f(1));  //1
        Console.WriteLine(f(5));  //5
        Console.WriteLine(f(10)); //12
        Console.WriteLine(f(20)); //312
        Console.WriteLine(f(42)); //6912
        Console.WriteLine(f(50)); //11313
    }
}

Answer 4

Jelly, 13 bytes

DµP;SðḍȦ
1Ç#Ṫ

1-based.
TryItOnline!

How?

DµP;SðḍȦ - Link 1, test a number
D        - convert to a decimal list
 µ       - monadic chain separation
   ;     - concatenate the
  P      -     product, and the
    S    -     sum
     ð   - dyadic chain separation
      ḍ  - divides n?
       Ȧ - all (i.e. both)

1Ç#Ṫ - Main link, get nth entry, 1-based: n
1 #  - find the first n matches starting at 1 of
 Ç   - the last link (1) as a monad
   Ṫ - tail (the ultimate result)

Answer 5

Perl 6, 44 bytes (0-indexed)

{grep({$_%%(.comb.sum&[*] .comb)},1..*)[$_]}

Explanation:

{                                          }  # A function, with an argument n (`$_`)
 grep(                           ,1..*)       # Filter the infinite list
      {$_                       }             # Check that the function's argument
         %%(                   )              # is divisible by
                     &                        # both:
            .comb.sum                         # - the sum of the digits
                      [*] .comb               # - the product of the digits
                                       [$_]   # Get the n-th value

Infinite lists ftw!

Answer 6

Actually, 20 bytes

Naive implementation of the sequence definition. Golfing suggestions welcome! Try it online!

u`;;$♂≈;Σ(%@π(%|Y`╓N

Ungolfing

         Implicit input n.
u        Increment n, so that we don't accidentally include 0 in the sequence.
`...`╓   Starting with x=0, return the first n+1 values of x where f(x) is truthy.
  ;;       Duplicate x twice.
  $♂≈      str(x) and convert each char (each digit) into an int. Call this digit_list.
  ;        Duplicate digit_list.
  Σ        Get sum(digit_list).
  (%       Get x % sum(digit_list), which returns 0 if sum is a divisor of x.
  @        Swap the other duplicate of digit_list to TOS.
  π        Get prod(digit_list).
  (%       Get x % prod(digit_list), which returns 0 if prod is a divisor of x.
  |        Get x % sum(digit_list) OR x % prod(digit_list).
  Y        Logical negate, which only returns 1 if both are divisors, else 0.
N        Return the last value in the list of x where f(x) is truthy,
          that is, the nth value of the sequence.

Answer 7

R, 132 115 bytes

New version thanks to @Billywob nice comments !

n=scan();b=i=0;while(i<n){b=b+1;d=strtoi(el(strsplit(c(b,""),"")));if(na.omit(c(!b%%sum(d)&!b%%prod(d),0)))i=i+1};b

Ungolfed :

n=scan()
b=i=0

while(i<n)
    b=b+1;
    d=strtoi(el(strsplit(c(b,""),""))) #Splitting the number into its digits

    if(na.omit(c(!b%%sum(d)&!b%%prod(d),0)))
        i=i+1
b

Since R behave strangley with NAs, I had to add the whole ifelse(is.na(...)) part!
Or use na.omit(...)

Answer 8

Jellyfish, 45 bytes

p
\Ai
\&
>(&]&|0
  <*&d
 &~bN
  10
 ( )/+
 /*

Try it online!

Explanation

This is by far the most elaborate (and also the longest) program I've written in Jellyfish so far. I have no idea whether I'll be able to break this down in an understandable manner, but I guess I'll have to try.

Jellyfish provides a fairly general iteration operator, \, which helps a lot with "finding the Nth something". One of its semantics is "iterate a function on a value until a separate test function gives something truthy" (in fact, the test function receives both the current and the last element, but we'll only make it look at the current element). We can use this to implement a "next valid number" function. Another overload of \ is "iterate a function on a starting value N times". We can use our previous function and iterate it on 0 N times, where N is the input. All of that is set up fairly concisely with this part of the code:

p
\Ai
\&
>     0

(The reasons why 0, the actual input to the resulting function, is over there are a bit complicated and I won't go into them here.)

The issue with all of this is, that we won't be passing the current value to the test function manually. The \ operator will do this for us. So we now have construct a single unary function (via compositions, hooks, forks and currying) which takes a number and tells us whether it's a valid number (i.e. one which is divided by its digit sum and digit product). This is fairly non-trivial when you can't refer to the argument. Ever. It's this beauty:

 (&]&|
  <*&d
 &~bN
  10
 ( )/+
 /*

The ( is a unary hook, which means that it calls the function below (f) on its input (the current value x), and then passes both of them to the test function to the right (g), that is it computes g(f(x), x).

In our case, f(x) is another composite function which obtains a pair with the digit product and digit sum of x. That means g will be a function that has all three values to check if x is valid.

We'll start by looking at how f computes the digit sum and digit product. This is f:

 &~b
  10
 ( )/*
 /+

& is also composition (but the other way round). ~ is currying so 10~b gives function that computes the decimal digits of a number, and since we're passing that to & from the right, that's the first thing that will happen to the input x. The remainder uses this list of digits to compute their sum and product.

To compute a sum, we can fold addition over it, which is /+. Likewise, to compute the product we fold multiplication over it with /*. To combine both of these results into a pair, we use a pair of hooks, ( and ). The structure of this is:

()g
f

(Where f and g are product and sum, respectively.) Let's try to figure out why this gives us a pair of f(x) and g(x). Note that the right hook ) only has one argument. In this case, the other argument is implied to be ; which wraps its arguments in a pair. Furthermore, hooks can also be used as binary functions (which will be the case here) in which case they simply apply the inner function only to one argument. So really ) on a single function g gives a function that computes [x, g(y)]. Using this in a left hook, together with f, we obtain [f(x), g(y)]. This, in turn is used in a unary context, which mean that it's actually called with x == y and so we end up with [f(x), g(x)] as required. Phew.

That leaves only one thing, which was our earlier test function g. Recall that it will be called as g([p, s], x) where x is still the current input value, p is its digit product and s is its digit sum. This is g:

  &]&|
  <*&d
    N

To test divisibility, we'll obviously use modulo, which is | in Jellyfish. Somewhat unusually, it take its right-hand operand modulo its left-hand operand, which means that the arguments to g are already in the right order (arithmetic functions like this automatically thread over lists, so this will compute the two separate moduli for free). Our number is divisible by both the product and sum, if the result is a pair of zeros. To check whether that's the case, we treat the pair as a list of base-2 digits (d). The result of this is zero, only when both elements of the pair are zero, so we can negate the result of this (N) to obtain a truthy value for whether both values divide the input. Note that |, d and N are simply all composed together with a pair of &s.

Unfortunately, that's not the full story. What if the digit product is zero? Division and modulo by zero both return zero in Jellyfish. While this may seem like a somewhat odd convention, it actually turns out to be somewhat useful (because we don't need to check for zero before doing the modulo). However it also means we can get a false positive, if the digit sum does divide the input, but the digit product is zero (e.g. input 10).

We can fix this by multiplying our divisibility result by the digit product (so if the digit product is zero it will turn our truthy value into a zero as well). It turns out to be simpler to multiply the divisibility result with the pair of product and sum, and extract the result from the product afterwards.

To multiply the result with the pair, we kinda need to get back at an earlier value (the pair). This is done with a fork (]). Forks are kinda like hooks on steroids. If you give them two functions f and g, they represent a binary function which computes f(a, g(a, b)). In our case, a is the product/sum pair, b is the current input value, g is our divisibility test, and f is the multiplication. So all of this computes [p, s] * ([p, s] % x == [0, 0]).

All that's left now is to extract the first value of this, which is the final value of the test function used in the iterator. This is as simple as composing (&) the fork with the head function <, which returns the first value of a list.

Answer 9

Brachylog, 22 bytes

:1yt
#>=.@e+:I*.@e*:J*

Try it online!

Explanation

:1y                    Evaluate the first N valid outputs to the predicate below given the
                         main input as input
   t                   The output is the last one


#>=.                  Output is a strictly positive integer
    @e+               The sum of its digits…
       :I*.           …multiplied by an integer I results in the Output
           @e*        The product of its digits…
              :J*     …multiplied by an integer J results in the Output

Answer 10

JavaScript (ES6), 78

n=>eval("for(i=0;n;!p|i%s|i%p||n--)[...++i+''].map(d=>(s-=d,p*=d),s=0,p=1);i")

Less golfed

n=>{
  for(i=0; n; !p|i%s|i%p || n--)
    s=0,
    p=1,
    [...++i+''].map(d=>(s-=d, p*=d));
  return i
}  

Answer 11

Pyth, 18 bytes

e.f!.xs%LZsM*FBsM`

Try it online: Demonstration

Explanation:

e.f!.xs%LZsM*FBsM`ZZQ1   implicit variables at the end
e                        print the last number of the 
 .f                 Q1   first Q (input) numbers Z >= 1, which satisfy:
                 `Z         convert Z to a string, e.g. "124"
               sM           convert each digits back to a number, e.g. [1, 2, 4]
            *FB             bifurcate with product, e.g. [[1, 2, 4], 8]
          sM                take the sum of each, e.g. [7, 8]
       %LZ                  compute the modulo of Z with each number, e.g. [5, 4]
      s                     and add both numbers, e.g. 9
    .x             Z        if an exception occurs (mod 0), use number Z instead
   !                        test, if this number is zero

Answer 12

JavaScript (ES6), 72 bytes

k=>eval("for(n=0;(E=o=>n%eval([...n+''].join(o))!=0)`+`|E`*`||--k;)++n")

Demo

It tends to be slow for higher values, so I'm limiting it to 20 here.

let f =

k=>eval("for(n=0;(E=o=>n%eval([...n+''].join(o))!=0)`+`|E`*`||--k;)++n")

console.log(f(1));  // 1
console.log(f(5));  // 5
console.log(f(10)); // 12
console.log(f(20)); // 312

Answer 13

Haskell, 94 85 72 71 bytes

([n|n<-[0..],(==)=<<map(gcd n)$[product,sum]<*>[read.pure<$>show n]]!!)

1-indexed.

Thanks to @Zgarb for saving 13 bytes!

Thanks to @nimi for saving a byte!

Answer 14

MATL, 21 bytes

`@tFYAtswph\~?@]NG<]&

Long and inefficient...

Try it online!

How it works

`        % Do...while
  @      %   Push current iteration index (1-based)
  tFYA   %   Duplicate. Convert number to its digits
  ts     %   Duplicate. Sum of digits
  wp     %   Swap. Product of digits
  h\     %   Concatenate. Modulo. This gives a length-2 array
  ~?     %   If the two values are zero: we found a number in the sequence
    @    %     Push that number
  ]      %   End if
  NG<    %   True if number of elements in stack is less than input
]        % End do...while. If top of the stack is true: next iteration. Else: exit
&        % Specify only one input (top of stack) for implicit display

Answer 15

Wonder, 33 bytes

@:^#0(!>@!(| %#0sum#0)%#0prod#0)N

Zero-indexed. Usage:

(@:^#0(!>@!(| %#0sum#0)%#0prod#0)N)9

Explanation

More readable:

@
  iget #0 
    (fltr@
      not (or % #0 sum #0) % #0 prod #0
    ) N

Basically gets an infinite list of numbers divisible by its digital sum and product by filtering an infinite list of whole numbers through a predicate. Then the nth item is simply picked out of the list.

Answer 16

Python3, 134 80 Bytes

New version thanks to Flp.Tkc

t=input();h=k=0;p=int
def g(x,q=0,w=1):
    for i in x:X=p(x);I=p(i);q+=I;w*=I
    return w!=0and X%q+X%w<1
while h<p(t):k+=1;h+=g(str(k))

New code, I remembered a golfing way to do the factorial

f,t=lambda x:0**x or x*f(x-1),0
for i in str(f(int(input()))):t+=int(i)
print(t)

The code itself isn't very golf-like, more like brute force golf

def g(x):
    q=0;w=1;X=int(x)
    for i in x:I=int(i);q+=I;w*=I
    return (w!=0+ X%q==0and X%w==0)
t=input();h=k=0
while h<int(t):
    k+=1
    if g(str(k))is True:h+=1

g(x) is a function that returns True if x fits the criteria.

Answer 17

Python 2, 122 110 Bytes

def a(m,i=1,k=1):n=map(int,`i`);p=reduce(lambda x,y:x*y,n);k+=p and 1>i%sum(n)+i%p;return(k>m)*i or a(m,i+1,k)

1 indexed, you need to use a Python interpreter with a quite high recursion limit.

Answer 18

JavaScript (ES6), 70 bytes

k=(b,n=1,f=c=>n%eval([...n+''].join(c))!=0)=>f`+`|f`*`||--b?k(b,n+1):n

This turned out quite a bit like @Arnauld's answer, but recursion is apparently 2 bytes shorter. Works in Chrome, though it's very slow on inputs greater than 30 or so (50 takes 6 seconds).

Answer 19

C89, 381 226 195 170 169 bytes

1-indexed (same exact answers as in the challenge).

Assumes 4-byte (32 bit) int (most modern architectures).

I genuinely believe this can't go any shorter.

x,c,*b,m,t,i,a;g(n){for(b=malloc(0);c<n;b[c-1]=x++,t=1){char s[9];for(i=m=0;i<sprintf(s,"%d",x);m+=a,t*=a)a=s[i++]-48;b=m*t?x%m+x%t?b:realloc(b,4*++c):b;}return b[c-1];}

Function int g (int) leaks memory and accesses uninitialised memory once per call but doesn't segfault and returns the right number.

Full program that takes input in unary (./prog $(seq 1 10) for 10) with ungolfed (kinda):

x, c, * b, m, t, i, a;

g(n) {
 for (b = malloc(0); c < n; b[c - 1] = x++, t = 1) {
  char s[9];
  i = m = 0;
  for (; i < sprintf(s, "%d", x); m += a, t *= a) a = s[i++] - 48;
  b = m * t ? x % m + x % t ? b : realloc(b, 4 * ++c) : b;
 }
 return b[c - 1];
}

main (j) {
  printf("%d\n", g(--j));
}

Old answer:

C99, 381 bytes

#include <stdio.h>
#include <inttypes.h>
#include <string.h>
#include <stdlib.h>
#define U uint64_t
#define S size_t
S f(S n){U x=0;S c=1,l;U*b=malloc(sizeof(U));while(c<=n){char s[21];snprintf(s,20,"%"PRIu64,x);U m=0,t=1;l=strnlen(s,21);for(S i=0;i<l;i++){U a=(U)s[i]-48;m+=a,t*=a;}if(m*t?(!(x%m))&&(!(x%t)):0){b=realloc(b,sizeof(U)*++c);b[c-1]=x;}++x;}U o=b[n];free(b);return o;}

This can probably be golfed more.

Full program:

#include <stdio.h>
#include <limits.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

bool qualifies (const uint64_t);
size_t       f (const size_t);


int main(const int argc, const char* const * const argv) {
  (void) argc;
  size_t arg = strtoull(argv[1], NULL, 10);
  uint64_t a = f(arg);
  printf("a: %" PRIu64 "\n", a);
  return 0;
}

bool qualifies (const uint64_t num) {
  char s[21];
  snprintf(s, 20, "%" PRIu64 "", num);

  uint64_t sum  = 0,
           mult = 1;
  size_t    len = strnlen(s, 400);

  for (size_t i = 0; i < len; i++) {
    uint64_t a = (uint64_t) s[i] - 48;
    sum += a, mult *= a;
  }

  //printf("sum: %" PRIu64 "\nmult: %" PRIu64 "\n", sum, mult);
  return sum * mult ? (! (num % sum)) && (! (num % mult)) : false;
}

size_t f (const size_t n) {
  uint64_t x = 0;
  size_t s_len = 1;
  uint64_t* nums = malloc(sizeof (uint64_t) * s_len);

  while (s_len <= n) {
    if (qualifies(x)) {
      ++s_len;
      //printf("len: %zu\n", s_len);
      nums = realloc(nums, sizeof (uint64_t) * s_len);
      nums[s_len - 1] = x;
    }
    ++x;
  }

  uint64_t o = nums[n];
  free(nums);
  return o;
}

Answer 20

Julia, 81 bytes

n->(i=c=1;while c<n d=digits(i+=1);all(d.>0)&&i%sum(d)==i%prod(d)<1&&(c+=1)end;i)

This is an anonymous function that accepts an integer and returns an integer. To call it, give it a name. The approach is the obvious one: check every number until we've encountered n terms of the sequence. The all check is necessary to ensure we don't get a DivisionError from % when the product of the digits is 0.

Ungolfed:

function f(n)
    i = c = 1
    while c < n
        d = digits(i += 1)
        all(d .> 0) && i % sum(d) == i % prod(d) < 1 && (c += 1)
    end
    return i
end

Try it online! (includes all test cases)

Answer 21

C, 110 bytes

p;s;i;j;f(n){j=0;while(n){i=++j;p=1;s=0;do p*=i%10,s+=i%10;while((i/=10)>0);if(p>0&&j%p+j%s==0)--n;}return j;}

Ungolfed and usage:

p;s;i;j;
f(n){
 j=0;
 while(n){
  i=++j;
  p=1;
  s=0;
  do
   p*=i%10,   //product
   s+=i%10;   //sum
  while((i/=10)>0);
  //check if product is not zero since floating point exception
  if(p>0 && j%p + j%s == 0)--n;
 }
 return j;
}

int main(){
 int n;
 scanf("%d",&n);
 printf("\n%d\n", f(n));
}

Answer 22

PHP, 96 bytes

Takes n as a command line argument.

Golfed

for(;$i<$argv[1];)!($p=array_product($d=str_split(++$j)))|$j%array_sum($d)||$j%$p?:$i++;echo $j;

Ungolfed

for (; $i < $argv[1];)                             // Loop until we've found the nth number as pass by command line
    !($p = array_product($d = str_split(++$j))) || // Split our current number into its digits and assign that to a variable, then assign the product of that array to another variable.
                                                   // As well, we're checking if the product equals 0, to prevent an error from trying to mod by 0 later. The condition short circuits before it happens.
    $j % array_sum($d) ||                          // Check if the sum of the array is a divisor
    $j % $p                                        // Check if the product is a divisor
    ?: $i++;                                       // Increment the number of found instances only if all conditions are met.
echo $j;                                           // Output to screen.

Answer 23

PowerShell v2+, 84 bytes

param($n)for(;$n){$n-=!(++$a%(($b=[char[]]"$a")-join'+'|iex)+$a%($b-join'*'|iex))}$a

Iterative solution. Takes input $n and enters a for loop so long as $n is not zero. Each iteration, we subtract from $n the result of a Boolean statement, broken out below:

!(++$a%(($b=[char[]]"$a")-join'+'|iex)+$a%($b-join'*'|iex))
!(                                                        ) # Encapsulate in a NOT
  ++$a%                                                     # Increment $a and take mod ...
        ($b=[char[]]"$a")                                   # Turn $a into char-array, store in $b
                         -join'+'                           # Join the char-array together with +
                                 |iex                       # and eval it
                                      $a%($b-join'*'|iex)   # Similar for *
                                     +                      # Addition

Thus, only if $a%(sum) and $a%(product) are both equal to zero will the addition also be zero, and thus the Boolean-not will be True and therefore $n is decremented.

Once we exit the loop (i.e., we hit the nth term), we simply place $a on the pipeline, and output is implicit.

Examples

Note: This tosses a bunch of "Attempted divide by zero" errors to STDERR, which is ignored by default. I've explicitly added a 2>$null to the example below to cleanup the output. It's also pretty slow once it gets to about 30 or so, and 50 takes about 45 seconds on my machine.

PS C:\Tools\Scripts\golfing> 1,5,10,20,30,42,50|%{"$_ --> "+(.\numbers-divisible-by-sum-and-product.ps1 $_ 2>$null)}
1 --> 1
5 --> 5
10 --> 12
20 --> 312
30 --> 1344
42 --> 6912
50 --> 11313

Answer 24

BASH, 125 bytes

while ((n<$1));do
((i++))
p(){ fold -1<<<$i|paste -sd$1|bc;}
z=`p \*`
((z))&&[ $[i%`p +`]$[i%z] -eq 0 ]&&((n++))
done
echo $i