Is it a Harshad Number?

Question

A Harshad number is a number that is divisible by the sum of its digits. This is obviously dependent on what base the integer is written in. Base 10 Harshad numbers are sequence A005349 in the OEIS.

Your Task:

Write a program or function that determines whether a given integer is a Harshad number in a given base.

Input:

A positive integer <10^9, and a base between 2 and 36, OR, a positive integer in its base, using lowercase letters for the numbers from 11-36 and a base between 2 and 36. You only have to handle one of these options.

Output:

A truthy/falsy value indicating whether the first input is a Harshad number in the base of the second input.

Examples:

27,10 ----------> truthy
8,5 ------------> truthy
9,5 ------------> falsy
1a,12 OR 22,12 -> truthy

Scoring:

This is code-golf, lowest score in bytes wins.

Answer 1

Python 2, 46 bytes

lambda n,b:n%sum(n/b**i%b for i in range(n))<1

Try it online!

Answer 2

Jelly, 4 bytes

bSḍḷ

Try it online!

How it works

bSḍḷ  Main link. Arguments: n (integer), k (base)

b     Convert n to base k.
 S    Take the sum.
   ḷ  Left; yield n.
  ḍ   Test for divisibility.

Answer 3

Python 3, 73 bytes

def f(n,b):
 if b<2:return 1
 s=0;c=n
 while n:s+=n%b;n//=b
 return c%s<1

Try it online!

1 is truthy, you know.

Answer 4

Python 2, 54 47 bytes

n,k=input();m=n;s=0
exec's-=m%k;m/=k;'*n
1>>n%s

Time and memory complexity are O(n), so don't try 10⁹ on TIO.

Output is via exit code, so 0 is truthy, 1 is falsy. If this output method winds up being allowed, a further byte can be saved by turning the program into a function.

Thanks to @musicman523 for suggesting exit codes!

Try it online!

Answer 5

Dyalog APL, 20 bytes

{⍺=1:0⋄⍵|⍨+/⍺⊥⍣¯1⊢⍵}

Try it online! _{[15 first numbers in 15 first bases]}

Takes the number as a right argument and the base as a left argument, 0 is truthy.

How?

⍺⊥⍣¯1⊢⍵ - ⍵ in base ⍺ as a list of digits

⍵|⍨ - ⍵ modulo ...

+/ - the sum

Answer 6

Pyth, 12 7 bytes

!%hQsjF

Try it online!

Byte count is now lower since unary is no longer required.

Explanation

!%hQsjF
     jF    Fold the input over base conversion (converts given number to given base)
    s      Sum the values
  %hQ       Take the first input modulo that sum
!          Logical not, turning 0s from the modulus into True and all else into False

Answer 7

Husk, 5 bytes

¦ΣB²¹

Try it online!

Answer 8

R, 64 60 bytes

(requires the pryr package)

pryr::f({d=pryr::f('if'(n<b,n,n%%b+d(b,n%/%b)));!n%%d(b,n)})

This is an anonymous function that takes two arguments, b and n that evaluates to (which is on TIO):

function(b,n){
   d=function(b,n)
     if(n<b) n else n%%b + d(b,n%/%b)
   !n%%d(b,n)
}

where d computes the digit sum for the required base.

Dropped 4 bytes once the base was guaranteed to be greater than 1.

Try it online!

Answer 9

Japt, 9 bytes

vUsV ¬xnV

Takes input as two integers.

Try it online!

Answer 10

Java (OpenJDK 8), 54 bytes

n->b->{int s=0,c=n;for(;c>0;c/=b)s+=c%b;return n%s<1;}

Try it online!

Answer 11

Javascript (ES6), 68 67 bytes

n=>k=>!(n%eval([...n.toString(k)].map(_=>parseInt(_,k)).join('+')))

Note that since we are required only to handle either base-k or base-10 numbers for n, I assume n is a base-10 integer always.

-1 byte, thanks to TheLethalCoder!

How it works:

!                                    # Convert to true if 0 else false
 (n%                                 # Compute n modulo
    eval(                            # evaluate string
         [...n.toString(k)]          # convert to array of base-k divisors
         .map(_=>parseInt(_,k))      # map lowercase characters to ints
         .join('+')                  # join array as string of characters
    )                                # get the raw remainder, and let ! do its work
 ) 

Try it online!

Answer 12

K (ngn/k), 12 bytes

{~(+/y\x)!x}

Try it online!

A function taking an integer (x) and the base to use (y).

• y\x convert x to a base-y representation
• +/ take the sum of the digits
• ~(...)!x check if the sum of the digits mod the input integer is non-zero

Answer 13

Javascript ES6, 62 bytes

n=>b=>!(n%[...n.toString(b)].reduce((x,y)=>x+parseInt(x,b),0))

Answer 14

C (gcc), 37 bytes

f(n,b,i,s){n?f(n/b,b,i,s+n%b):i%s<1;}

Try it online!

Returns zero for true, non-zero for false.
I want to know, why not just i%s does work, but i%s<1 does (isn't that very strange?).

Answer 15

Perl 6, 40 bytes

{$^b>1??$^a%%[+] $a.polymod($b xx*)!!?1}

Test it

Expanded:

{  # bare block lambda with placeholder parameters ｢$a｣ and ｢$b｣

    $^b > 1          # declare ｢$b｣ and compare against 1

  ??                 # if ｢$b > 1｣ then:

      $^a            # declare ｢$a｣
    %%               # is it divisible by
      [+]            # reduce the following with &infix:<+> (sum)
        $a.polymod(
          $b xx *    # infinite list of ｢$b｣s
        )

  !!                 # if ｢$b <= 1｣ then:

    ? 1              # Boolify 1 (shorter than True)
}

Answer 16

Mathematica, 30 bytes

#2<2||Tr@IntegerDigits@##∣#&

Pure function taking two arguments, the integer and the base (in that order), and returning True or False. Careful: the first two |s are just the normal ASCII character, while the last ∣ is U+2223.

#2<2 deals with the special case of base 1. Otherwise, Tr@IntegerDigits@## produces the sum of the digits of the first argument when written in the base of the second argument, and ...∣# tests whether that sum divides the first argument.

Answer 17

Batch, 119 bytes

@if %2==1 echo 1&exit/b
@set/at=%1,s=0
:l
@if %t% gtr 0 set/as+=t%%%2,t/=%2&goto l
@set/at=%1%%s
@if %t%==0 echo 1

Outputs 1 for Harshad numbers.

Answer 18

Python 3, 45 bytes

lambda n,b:int(n,b)%sum(int(i,b)for i in n)<1

Try it online!

Based on the updated formats for input.

Answer 19

C (gcc), 57 bytes

f(n,b,t,s){while(b>1&&t){s+=t%b;t/=b;}return b<2||n%s<1;}

Try it online!

Answer 20

Pari/GP, 25 bytes

(n,b)->n%sumdigits(n,b)<1

Try it online!

Answer 21

Japt -!, 5 bytes

%ìV x

Try it

Answer 22

C (gcc), 49 43 bytes

a,b;f(x,n){for(a=x,b=0;b+=x%n,x/=n;);a%=b;}

Try it online!

Returns zero for true, non-zero for false.

It is very simple. It just accumulates all the digits of x in b and returns x % b.

Ungolfed version:

// local variables
int a, b;
int f(int x, int n)
{
    // Accumulate all digits in b
    // Note that the for loop only checks x /= n
    for (a = x, b = 0; b += x % n, x /= n;)
        ;
    // Then return a % b.
    return a % b;
}

Thanks to dingledooper for the -6 bytes!

Answer 23

x86 Machine Code, 19 bytes

50 31 C9 99 F7 F6 01 D1 85 C0 75 F7 58 99 F7 F1 85 D2 C3

The above bytes define a function that accepts the value in the EAX register and the base in the ESI register, and sets the zero flag (ZF) based on whether the value is a Harshad number (ZF will be clear if the value is a Harshad number).

Note that this is a custom calling convention, defined expressly for the purposes of this challenge. Assembly/machine language programmers are allowed to do that. However, note further that the choice of the ESI register for the second parameter (base) is completely arbitrary. This can be changed to any other unused general-purpose integer register (i.e., EBX, EDI, or EBP) without affecting either correctness or code size.

Try it online!

In ungolfed assembly language mnemonics:

; bool IsHarshadNumber(unsigned value, unsigned base)
;
; Inputs:
;    EAX = input value
;    ESI = base
; Outputs:
;    ZF = 0 if Harshad number; otherwise, ZF = 1
; Clobbers:
;    EAX, EDX, ECX
;
        IsHarshadNumber:
50         push   eax             ; preserve input value
31 C9      xor    ecx, ecx        ; zero-out accumulator

        Accumulate:               ; <----------------------------------------------------\
99         cdq                    ; zero-out EDX (based on EAX) to prepare for division  |
F7 F6      div    esi             ; divide by base (EAX = quotient; EDX = remainder)     |
01 D1      add    ecx, edx        ; accumulate remainder                                 |
85 C0      test   eax, eax        ; is quotient 0?                                       |
75 F7      jnz    Accumulate      ; keep looping until it is ----------------------------/

58         pop    eax             ; restore input value
99         cdq                    ; zero-out EDX (based on EAX) to prepare for division
F7 F1      div    ecx             ; divide by accumulator
85 D2      test   edx, edx        ; set ZF based on remainder
C3         ret
```

Answer 24

Ruby, 43 bytes

->n,b,s=0,i=n{(s+=n%b;n/=b)while n>0;i%s<1}

Try it online!

---

Ruby, 43 bytes

f=->n,b,s=0,i=n{n>0?f[n/b,b,s+n%b,i]:i%s<1}

Try it online!

Answer 25

JavaScript (Node.js), 41 bytes

f=(n,b,s=0,i=n)=>n?f(n/b|0,b,s+n%b,i):i%s

Try it online!

Returns zero for true, non-zero for false.