12
\$\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\$
1

25 Answers 25

12
\$\begingroup\$

Python 2, 46 bytes

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

Try it online!

\$\endgroup\$
0
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\$
5
  • \$\begingroup\$ OK, definition of FGITW right here. Impressive though. How do you do these things? \$\endgroup\$
    – Gryphon
    Jul 11, 2017 at 17:50
  • \$\begingroup\$ It's fairly easy with a base conversion built-in. \$\endgroup\$
    – Dennis
    Jul 11, 2017 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, 2017 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, 2017 at 17:56
  • \$\begingroup\$ Oh, I see. I thought b just converted n into an integer in base k. \$\endgroup\$
    – Gryphon
    Jul 11, 2017 at 17:58
4
\$\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\$
7
  • \$\begingroup\$ -3 bytes in Python 2. \$\endgroup\$
    – notjagan
    Jul 11, 2017 at 18:10
  • \$\begingroup\$ @notjagan I don't use Python 2 \$\endgroup\$
    – Leaky Nun
    Jul 11, 2017 at 18:12
  • \$\begingroup\$ -7 bytes in Python 2 (works in Python 3 if you redefine ∈put∈putinput to use Python 2's semantics, which is allowed, and change / to // for a 1-byte cost), using a full program with exit code returns \$\endgroup\$ Jul 11, 2017 at 18:13
  • \$\begingroup\$ @musicman523. In a different version, with 7 bytes shaved off, I would just post that myself. \$\endgroup\$
    – Gryphon
    Jul 11, 2017 at 18:15
  • \$\begingroup\$ @Gryphon I didn't come up with the actual code, though; I'm working on my own answer now. \$\endgroup\$ Jul 11, 2017 at 18:16
4
\$\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\$
3
  • \$\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\$ Jul 11, 2017 at 18:52
  • \$\begingroup\$ Found something even shorter, thanks to your suggestion. :) \$\endgroup\$
    – Dennis
    Jul 11, 2017 at 19:03
  • \$\begingroup\$ Nice! I thought maybe you could incur a ZeroDivisionError, but your way is shorter I believe \$\endgroup\$ Jul 11, 2017 at 19:06
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\$

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\$
3
\$\begingroup\$

Husk, 5 bytes

¦ΣB²¹

Try it online!

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

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\$
1
  • 1
    \$\begingroup\$ Shown as curried, TIO as non-curried. \$\endgroup\$ Jul 12, 2017 at 13:18
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\$
2
  • 4
    \$\begingroup\$ Welcome to the site! :) \$\endgroup\$
    – DJMcMayhem
    Jul 12, 2017 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\$ Jul 12, 2017 at 10:29
2
\$\begingroup\$

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

Javascript ES6, 62 bytes

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

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?).

\$\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\$
1
  • \$\begingroup\$ Is passing extra parameters allowed? Or is it the only way here.. \$\endgroup\$
    – vrintle
    Dec 31, 2020 at 11:42
0
\$\begingroup\$

Pari/GP, 25 bytes

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

Try it online!

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

Japt -!, 5 bytes

%ìV x

Try it

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

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You may use the return hack to achieve 43 bytes. \$\endgroup\$ Dec 30, 2020 at 21:51
  • \$\begingroup\$ Thanks! [undefined behavior intensifies] \$\endgroup\$
    – EasyasPi
    Dec 30, 2020 at 22:28
0
\$\begingroup\$

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

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!

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.