Find the nth number where the digit sum equals the number of factors

Question

(This is OEIS A057531.)

Your task

Given a positive integer, \$n\$, find the \$n\$^th number where the digit sum equals the number of factors

Explanation

For example, let's take 22:

Its factors are \$[1, 2, 11, 22]\$ (length: 4).

Its digit sum is 4.

This means that it is a number where the digit sum equals the number of factors.

The series

The first few terms of this series are:

\$[1, 2, 11, 22, 36, 84, 101, 152, 156, 170]\$

Test cases

Note: these are 1-indexed. You may use 0-indexing.

Input  Output
1      1
2      2
3      11
4      22
5      36
10     170
20     444
30     828
40     1111
50     1548
100    3588

Clarifications

• You may use either 0-indexing or 1-indexing
• The sequence starts from 1, not from 0
• The factors of a number include 1 and the number itself
• Default sequence rules apply - you may output the first \$n\$ terms, or the infinite sequence, or something else
• This is code-golf, so shortest answer in bytes wins!

Answer 1

Factor + lists.lazy math.unicode project-euler.common, 54 bytes

[ 1 lfrom [ dup >dec 48 v-n Σ swap tau* = ] lfilter ]

Try it online!

Returns an infinite lazy list of the sequence.

• 1 lfrom The natural numbers
• [ ... ] lfilter Take the ones where...
• >dec 48 v-n Σ Digit sum
• tau* Divisor count
• = Are equal

Answer 2

Raku, 39 bytes

grep {.comb.sum==grep $_%%*,1..$_},1..*

Try it online!

This is an expression for the lazy, infinite sequence of values.

Answer 3

PARI/GP, 44 bytes

for(i=1,oo,sumdigits(i)-numdiv(i)||print(i))

Attempt This Online!

Prints the sequence forever.

Answer 4

Jelly, 8 bytes

1DS=ÆdƲ#

Try it online!

Takes \$n\$ on STDIN, and outputs the first \$n\$ values.

How it works

1DS=ÆdƲ# - Main link. Takes no arguments
      Ʋ  - Group the previous 4 links into a monad f(k):
 D       -   Digits of k
  S      -   Sum
    Æd   -   Divisor count of k
   =     -   Are they equal?
1      # - Read n from STDIN and find the first n k≥1 such that f(k) is true

Answer 5

Wolfram Language (Mathematica), 66 bytes

(k=t=0;While[k<#,If[Tr[1^Divisors@++t]==Tr@IntegerDigits@t,k++]])&

Try it online!

Answer 6

Ruby, 55 51 bytes

-4 bytes thanks to G B

1.step{|a|a.digits.sum==(1..a).count{a%_1<1}&&p(a)}

Attempt This Online!

Answer 7

Python 3, 69 bytes

n=1
while sum(n%~d//n+n//10**-~d*9for d in range(n))or[print(n)]:n+=1

Try it online!

Would print forever if I hadn't doctored the print function in the preamble.

Based on @Arnauld's answer.

This uses two additional little tricks:

1. sum _d=1..n n%-d // n equals number of divisors - n
2. sum _d=1.. n // 10^d x 9 equals n - digit sum

Answer 8

JavaScript (V8),  60 59  58 bytes

Prints the sequence 'forever' (that is, until the call stack overflows).

for(n=0;g=d=>d&&!(n%d--)-~~(n+g)[d]+g(d);)g(++n)||print(n)

Try it online!

Commented

We use a recursive function which simultaneously counts the number of divisors and subtracts the sum of the digits.

for(           // infinite loop:
  n = 0;       //   start with n = 0
  g = d =>     //   g is a recursive function taking a divisor d
  d &&         //   stop if d = 0
  !(n % d--) - //   add 1 if d is a divisor of n
  ~~(n + g)    //   coerce n to a string with some additional
               //   non-digit characters
  [d] +        //   subtract the d-th digit (0 if out of bounds)
  g(d);        //   add the result of a recursive call
)              //
g(++n)         // increment n; initial call to g with d = n
|| print(n)    // print n if the result is 0

---

Python 3, 78 bytes

-1 thanks to @Mukundan314

A port of my initial JS code. Most probably sub-optimal.

f=lambda d,v:d and(n%d<1)-v%10+f(d-1,v//10)
n=1
while 1:f(n,n)or print(n);n+=1

Try it online!

Answer 9

Japt, 11 bytes

Èâ ʶXìx}iU

Try it

Èâ ʶXìx}iU     :Implicit input of integer U
È               :Function taking an integer X as argument
 â              :  Divisors
   Ê            :  Length
    ¶           :  Equal to
     Xì         :    Digit array
       x        :    Reduced by addition
        }       :End function
         iU     :Get the Uth integer >=0 that returns true

Answer 10

Vyxal, 7 bytes

KLn∑=)ȯ

Try it Online!

      ȯ # First n integers
-----)  # Where...
 L      # Length of
K       # Factor count
    =   # Equals
  n∑    # Digit sum

Answer 11

Charcoal, 27 bytes

ＮθＷ‹№υ¹θ⊞υ⁼ΣＬυΣＥυ¬﹪Ｌυ⊕λＩ⊖Ｌυ

Try it online! Link is to verbose version of code. Outputs the nth term. Explanation:

Ｎθ

Input n.

Ｗ‹№υ¹θ

Repeat until n terms have been found.

⊞υ⁼ΣＬυΣＥυ¬﹪Ｌυ⊕λ

Determine whether the current length of the predefined empty list is a member of the sequence, and push the result to the predefined empty list. Note that this has been written in such a way that it thinks 0 is not a member of the sequence, although an alternative interpretation could have included it.

Ｉ⊖Ｌυ

Output the index of the last element in the list, which is therefore the nth term. (At a cost of 1 byte, this could be Ｉ⌕Ａυ¹ to output the first n terms.)

Answer 12

Retina, 68 bytes

K`
"$+"{`^
_
{`^
_$'¶$.'¶
\d
*
w`\b(_+)(?=\1*$)
_
_(¶_+)\1$

))0G`
_

Try it online! No test suite due to the way the program uses history. Explanation:

K`

Clear the buffer.

"$+"{`
)`

Repeat the original input number times.

^
_

Increment the value in the buffer.

{`
)`

Repeat until the buffer stops changing.

^
_$'¶$.'¶

Make three copies of the buffer; increment the first, and convert the second to decimal.

\d
*

Convert each digit separately back to unary, thus computing the sum of the digits.

w`\b(_+)(?=\1*$)
_

Count the number of factors in the current value.

_(¶_+)\1$

If the digit sum equals the factor count then decrement the first value again, causing the inner loop to exit.

0G`

Keep only the first value.

_

Convert the final value to decimal.

Answer 13

Python, ⁸⁰ 77 bytes

i=1
while[sum(map(int,str(i)))-sum(i%-~j<1for j in range(i))or print(i)]:i+=1

Attempt This Online!

-3 bytes thanks to @Jonathan Allan

Answer 14

Excel (ms365), 170 bytes

=INDEX(REDUCE(0,ROW(1:1048576),LAMBDA(a,b,IF(COUNT(REDUCE(0,SEQUENCE(b),LAMBDA(x,y,IF(MOD(b,y),x,VSTACK(x,y)))))-1=SUM(--MID(b,SEQUENCE(LEN(b)),1)),VSTACK(a,b),a))),A1+1)

Here ROW(1:1048576) will represent n and is the extend to which Excel can go (max rows). You'll notice that calculation wise the nesting will likely not compute but to be fair to the challenge of any possible positive integer I had to include this number. 'Much easier' to compute and able to calculate any of the given samples would be ROW(1:3588):

What happens is:

• The outer REDUCE() will cycle through all possible integers in Excel-rows. It will VSTACK() any integer which follows the following rule;

• The inner REDUCE() will VSTACK() all integers in iteration if they equal zero when MOD() is applied and the SUM() of the numbers used in the integer equals the COUNT() of these stacked integers (I hope that is clear);

• INDEX() will then return a zero-based (hence the +1) integer from the VSTACK(). If you wish to return an array of the 1st n integers:

  =DROP(TAKE(REDUCE(0,ROW(1:500),LAMBDA(a,b,IF(COUNT(REDUCE(0,SEQUENCE(b),LAMBDA(x,y,IF(MOD(b,y),x,VSTACK(x,y)))))-1=SUM(--MID(b,SEQUENCE(LEN(b)),1)),VSTACK(a,b),a))),A1+1),1)
  

Answer 15

x86-64 machine code, 39 bytes

31 C0 FF C0 31 F6 6A 0A 59 50 99 F7 F9 29 D6 01 C2 75 F7 58 89 C1 50 F7 F9 58 83 EA 01 99 11 D6 E2 F4 19 D7 79 DC C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a number n in EDI and returns the 0-indexed nth number where the digit sum equals the number of factors in EAX.

In assembly:

f:  xor eax, eax    # Set EAX to 0. EAX will be the number currently being tested.
nextnum:
    inc eax         # Increase EAX by 1.
    xor esi, esi    # Set ESI to 0.
    push 10; pop rcx# Set RCX (the 64-bit register containing ECX) to 10.
    push rax        # Save the value of RAX (containing EAX) onto the stack.
digitloop:
    cdq             # Set EDX to 0 by sign-extending EAX.
    idiv ecx        # Divide EDX:EAX by ECX (10).
                    # The quotient goes in EAX and the remainder goes in EDX.
    sub esi, edx    # Subtract EDX (the remainder; a digit of the number) from ESI.
    add edx, eax    # Add EAX to EDX.
    jnz digitloop   # Jump back if the result of the addition is nonzero.
            # This loop will exit when the quotient and remainder are both zero.
            # This performs one more iteration than otherwise necessary,
            # so that EDX will be 0 after the loop, which will be useful later.
    pop rax         # Restore the value of RAX from the stack.
    mov ecx, eax    # Set ECX to the same value, the number being tested.
                    #  (The higher bits of RCX are automatically zeroed.)
factorloop:
    push rax        # Save the value of RAX onto the stack.
    idiv ecx        # Divide EDX:EAX by ECX; quotient in EAX, remainder in EDX.
    pop rax         # Restore the value of RAX from the stack.
    sub edx, 1      # Subtract 1 from EDX. The carry flag CF becomes 1 iff EDX=0.
    cdq             # Set EDX to 0 by sign-extending EAX.
    adc esi, edx    # Add EDX+CF to ESI, increasing it by 1 with each factor found.
    loop factorloop # Decrease RCX by 1, and jump back if it's nonzero.
    sbb edi, edx    # Subtract EDX+CF from EDI.
                    # 1 is the last value checked, and it is always a factor.
                    # Thus, the last ADC added 1 to ESI, and CF=1 iff ESI went
                    #  from -1 to 0; iff the number satisfies the condition.
    jns nextnum     # Jump back if the result is nonnegative.
    ret             # Return.

Answer 16

05AB1E, 8 bytes

∞ʒÑgySOQ

Outputs the infinite sequence.

Try it online.

Explanation:

∞       # Push an infinite positive list: [1,2,3,...]
 ʒ      # Filter it by:
  Ñ     #  Get a list of divisors of the current integer
   g    #  Pop and push its length
  yS    #  Push the current integer again, and convert it to a list of digits
    O   #  Take the sum of those digits
     Q  #  Check if the amount of digits equals the digit-sum
        # (after which the filtered infinite list is output implicitly as result)

Answer 17

MathGolf, 10 bytes

î·─£\Σ=╛p▲

Outputs the infinite sequence, with each term on a separated line.

Try it online.

Explanation:

         ▲  # Do-while true with pop:
î           #  Push the 1-based loop index
 ·          #  Quadruplicate it
  ─         #  Pop one, and get a list of its divisors
   £        #  Pop this list, and get its length
    \       #  Swap to put another 1-based index at the top of the stack
     Σ      #  Sum its digits
      =     #  Check if the amount of divisors and sum of digits are equal
       ╛    #  If this is truthy:
        p   #   Print a 1-based index with trailing newline

Answer 18

R, 53 bytes

while(F<-F+1)sum(F%/%10^(0:F)%%10,-!F%%1:F)||print(F)

Try it online!

Prints the sequence indefinitely (in theory). In practice, results over 308 are inaccurate as then 10^(0:F) exceeds computing capabilities of R. We could counter this by using eg. 10^(0:nchar(F)), but this costs bytes...

Explanation:

while(F<-F+1)          # while increasing value of F (infinitely)
sum(F%/%10^(0:F)%%10,  # sum the digits of F (with a lot of unnecessary 0s)
-!F%%1:F)              # minus the count of divisors of F
||print(F)             # if the result is 0, print F

Answer 19

Brachylog, 10 bytes

ℕ₁≜.ẹ+~l~f

Try it online!

This is a generator. The TIO link has a header to ask for the first 10 possible instantiations of the output.

Explanation

ℕ₁≜.          The output is an instantiated natural integer
    .ẹ+        The sum of elements (i.e. digits) of the output…
       ~l      …is the length of a list…
         ~f    …which is the list of factors of the output

Answer 20

Nibbles, 9 bytes (18 nibbles)

|,~~`^+`@~$,|,$~%@

|                   # filter
 ,~                 # 1..infinity
   ~                # for each number n that is falsy for
    `^              # bitwise xor of
      +             #   sum of
       `@ $         #   digits of n in base
         ~          #   10 (default)
                    # and
           ,        #   length of
             ,$     #   1..n
            |       #   filtered for each i that is
               ~    #   falsy for
                %@  #   n modulo i 

Answer 21

Excel, ¹¹² 110 bytes

LET(r,ROW(1:999),REDUCE("",r,LAMBDA(a,b,a&IF(SUM(MID(b,SEQUENCE(LEN(b)),1)+0)=SUM((MOD(b,r)<1)+0),b&",",""))))

Answer 22

Pyth, 15 bytes

.fqsjZTl{m*FdyP

Try it online!

Outputs the first \$n\$ terms as a list.

Explanation

.fqsjZTl{m*FdyP   | Full program
.fqsjZTl{m*FdyPZQ | with implicit variables
------------------+---------------------------------------------------------------
.f              Q | Find the first <input> integers Z (starting with 1) such that:
   s              |   the sum of
    jZT           |    the base 10 digits of Z
  q               |  equals
       l          |   the length of
                  |    the list of factors of Z, i.e.:
        {         |    the unique
         m*Fd     |     products of
             y    |      all subsets of
              PZ  |       the prime factors of Z

Answer 23

PLIS -i, 78 bytes

1+@(H@({$0*$0}{([$0+$1]{$0%10}[$0/10](M*$0))@(spT@$0)-[$0+$1](H@($0%a))@$0}a))

The -i flag generates sequence entries infinitely, as such:

C:\Users\conorob\Programming\langs\PLIS (main -> origin)
λ plis -i -f example\digit-sum-equal-factor-count.min.plis
1 2 11 22 36 84 101 152 156 170 202 208 225 228 288 301 372 396 441 444 468 516 525 530
602 684 710 732 804 828 882 952 972 1003 1016 1034 1070 1072 1106 1111 1164 1236 ^C

PLIS is a programming language which primarily manipulates data using relevant OEIS sequences. While it has a lot of OEIS sequences implemented, PLIS does not aim to trivialize CGCC challenges by implementing random challenge sequences, hence the length.

Because OEIS sequences are the primary functions in this language, whenever a sequence of word characters are encountered, they are interpreted as a base 53 integer encoded using the alphabetic characters and _. (The OEIS sequence quoted in the OP, A057531, would be represented as _ZU, were it actually implemented in the language.)

Here is a commented, ungolfed explanation of what the code generally does.

# add 1 to each
1 +
# find indices where the sequence is nonzero
@(
  A000007@(
    # square each difference
    {$0*$0}
      # over each positive integer
      {
        # digit sum
        ([$0+$1] {$0%10} [$0/10] (A000012*$0))@(A055642@$0)
        -
        # factor count
        [$0+$1](A7@($0%A000027))@$0
      } A000027)
  )

Answer 24

C (gcc), ⁸⁴ 83 bytes

• -1 byte thanks to ceilingcat!!

j,c;f(i){for(j=c=1;j<i;)c+=i%j++<1;for(;j;j/=10)c-=j%10;c||printf("%d ",i);f(i+1);}

Try it online!

Answer 25

Fig, \$10\log_{256}(96)\approx\$ 8.231 bytes

FmC'=SxLJk

Try it online!

Returns/prints the infinite list of such numbers.

FmC'=SxLJk
F          # Filter
 mC        # The infinite list of numbers
   '       # Where
     Sx    # The digit sum
    =      # Equals
       L   # The length
        Jk # Of its divisors + itself

Answer 26

Pip Classic, 35 18 bytes

W++xI$+x=0Nx%\,xPx

Try it online!

A lot of bytes saved thanks to @DLosc!

Answer 27

Stax, 9 bytes

▐ë<of▌ëÇ@

Run and debug it

This is PackedStax, which unpacks to:

Stax (unpacked), 11 bytes

VIf:d%_E|+=

Run and debug it

VI          # infinity
  f         # filtered by
   :d%      # the length of the divisors
      _E|+  # and the digit sum
          = # are equal

Answer 28

Haskell, 73 bytes

s=[n|n<-[0..],length[d|d<-[1..n],0==mod n d]==(sum.map(read.pure).show)n]

Try it online!

Answer 29

Scala, 83 71 bytes

Saved 12 bytes thanks to the comment of @naffetS

---

Golfed version. Try it online!

for(a<-1 to l)if(s"$a".map(_-'0').sum==(1 to a).count(a%_<1))println(a)

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val limit = 1000 // You can replace this with any limit you want
    for (a <- 1 to limit) {
      val sumOfDigits = a.toString.map(_.asDigit).sum
      val numFactors = (1 to a).count(a % _ == 0)
      if (sumOfDigits == numFactors) println(a)
    }
  }
}

Answer 30

Rockstar, 168 bytes

Rockstar can't do anything the challenge asks. So, of course, I'm going to do it anyway! On my phone!

listen to N
X's 0
while N
let X be+1
Y's 0
D's 0
while X-Y
let Y be+1
let M be X/Y
turn up M
let D be+M's X/Y

cut X in L
while L
let D be-roll L

let N be-D's 0

say X

Try it here (Code will need to be pasted in)

listen to N      :Read input string into variable N
X's 0            :Initialise X as 0
while N          :While N is not 0
let X be+1       :  Increment X
Y's 0            :  Initialise Y as 0
D's 0            :  Initialise D as 0
while X-Y        :  While Y is less than X
let Y be+1       :    Increment Y
let M be X/Y     :    Assign X/Y to variable M
turn up M        :    Round M up to nearest integer
let D be+        :    Increment D by
  M's X/Y        :      Is M equal to X/Y?
                 :  End while loop
cut X in L       :  Split X into a digit array and assign to variable L
while L          :  While L is not empty
let D be-        :    Decrement D by
  roll L         :      Pop the first element from L
                 :  End while loop
let N be-        :  Decrement N by
  D's 0          :    Is D equal to 0?
                 :End while loop
say X            :Output X