8
\$\begingroup\$

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 , lowest score in bytes wins.

\$\endgroup\$

17 Answers 17

11
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ OK, definition of FGITW right here. Impressive though. How do you do these things? \$\endgroup\$ – Gryphon Jul 11 '17 at 17:50
  • \$\begingroup\$ It's fairly easy with a base conversion built-in. \$\endgroup\$ – Dennis Jul 11 '17 at 17:53
  • \$\begingroup\$ I'm just impressed by the built-in to take the sum of the digits. Didn't even know that was a thing. \$\endgroup\$ – Gryphon Jul 11 '17 at 17:55
  • \$\begingroup\$ There's no built-in to take the sum of the digits. b converts n into the array of its base-k digits, then S takes its sum. \$\endgroup\$ – Dennis Jul 11 '17 at 17:56
  • \$\begingroup\$ Oh, I see. I thought b just converted n into an integer in base k. \$\endgroup\$ – Gryphon Jul 11 '17 at 17:58
10
\$\begingroup\$

Python 2, 46 bytes

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

Try it online!

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This seems to just continuously run for a base of 1. \$\endgroup\$ – Gryphon Jul 11 '17 at 18:02
  • \$\begingroup\$ @Gryphon done . \$\endgroup\$ – Leaky Nun Jul 11 '17 at 18:08
  • \$\begingroup\$ Sorry about the added bytes :( \$\endgroup\$ – Gryphon Jul 11 '17 at 18:09
  • \$\begingroup\$ Python isn't really the language for this. \$\endgroup\$ – Gryphon Jul 11 '17 at 18:09
  • \$\begingroup\$ -3 bytes in Python 2. \$\endgroup\$ – notjagan Jul 11 '17 at 18:10
3
\$\begingroup\$

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

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

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 109 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!

\$\endgroup\$
  • \$\begingroup\$ Can you change the language to "Python 2 interpreter" and use exit(n%s) where 0 is truthy and anything else is falsy? \$\endgroup\$ – musicman523 Jul 11 '17 at 18:52
  • \$\begingroup\$ Found something even shorter, thanks to your suggestion. :) \$\endgroup\$ – Dennis Jul 11 '17 at 19:03
  • \$\begingroup\$ Nice! I thought maybe you could incur a ZeroDivisionError, but your way is shorter I believe \$\endgroup\$ – musicman523 Jul 11 '17 at 19:06
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Japt, 9 bytes

vUsV ¬xnV

Takes input as two integers.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to the site! :) \$\endgroup\$ – DJMcMayhem Jul 12 '17 at 0:48
  • 1
    \$\begingroup\$ Take input in currying syntax to save a byte i.e. n=>k=>..., would be called like (345)(10) \$\endgroup\$ – TheLethalCoder Jul 12 '17 at 10:29
  • \$\begingroup\$ @TheLethalCoder Thanks! I updated. \$\endgroup\$ – Akshat Mahajan Jul 12 '17 at 18:29
1
\$\begingroup\$

Javascript ES6, 62 bytes

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

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)
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 25 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Shown as curried, TIO as non-curried. \$\endgroup\$ – Olivier Grégoire Jul 12 '17 at 13:18

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.