12
\$\begingroup\$

(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 rules apply - you may output the first \$n\$ terms, or the infinite sequence, or something else
  • This is , so shortest answer in bytes wins!
Improve this question
\$\endgroup\$
2

30 Answers 30

Reset to default
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Raku, 39 bytes

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

Try it online!

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

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

PARI/GP, 44 bytes

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

Attempt This Online!

Prints the sequence forever.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ That was quick! \$\endgroup\$
    – The Thonnu
    Nov 27, 2022 at 17:10
  • \$\begingroup\$ @TheThonnu Jelly's # builtin is very good for challenges along the lines of "Find the first n integers such that <thing> is true" \$\endgroup\$
    – caird coinheringaahin g ♦
    Nov 27, 2022 at 17:13
  • \$\begingroup\$ Hmm time to steal this builtin for myself :P \$\endgroup\$
    – Seggan
    Nov 28, 2022 at 17:58
4
\$\begingroup\$

Wolfram Language (Mathematica), 66 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @GB Nice work. Thanks! \$\endgroup\$
    – Jordan
    Nov 27, 2022 at 21:51
4
\$\begingroup\$

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 // 10d x 9 equals n - digit sum
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 7 bytes

KLn∑=)ȯ

Try it Online!

      ȯ # First n integers
-----)  # Where...
 L      # Length of
K       # Factor count
    =   # Equals
  n∑    # Digit sum
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python, 80 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

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Sae two bytes using subtraction and or - ATO \$\endgroup\$
    – Jonathan Allan
    Nov 27, 2022 at 18:37
  • 1
    \$\begingroup\$ ...and another moving the test and print into the while clause using the trick of placing the result inside a list - ATO \$\endgroup\$
    – Jonathan Allan
    Nov 27, 2022 at 18:59
  • 1
    \$\begingroup\$ alternatively, instead of doing a-b or c, you can do a==b==c (same length here), \$\endgroup\$
    – naffetS
    Nov 27, 2022 at 23:51
3
\$\begingroup\$

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):

enter image description here

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)

enter image description here

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm sure this can be golfed further :-) =LET(a,MAKEARRAY(10000,1,LAMBDA(r,c,IF(SUM(MID(r,SEQUENCE(LEN(r)),1)+0)=SUM(IF(MOD(r,SEQUENCE(r))<1,1,0)),r,0))),FILTER(a,a>0)) \$\endgroup\$
    – jdt
    Nov 29, 2022 at 13:29
  • \$\begingroup\$ @jdt, I made it hard on myself I see. Your option deserves an answer on its own. Very neat. \$\endgroup\$
    – JvdV
    Nov 29, 2022 at 13:37
3
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

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

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

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

enter image description here

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Excel, 112 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&",",""))))

enter image description here

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Wow, I came across the exact same solution! Mind if I edit the explanation a bit? \$\endgroup\$
    – hakr14
    Nov 29, 2022 at 21:04
  • \$\begingroup\$ Be my guest, I didn't spend too much time on the explanation. I've always loved that about Pyth, sometimes it feels less like programming and more like just uncovering the optimal solution (not that this is optimal, but who knows) \$\endgroup\$
    – CursorCoercer
    Nov 29, 2022 at 21:40
2
\$\begingroup\$

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)
  )
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Did you just create this language today? (Completely fine, but just asking) \$\endgroup\$
    – The Thonnu
    Dec 2, 2022 at 20:03
  • 1
    \$\begingroup\$ @TheThonnu I've been working on it the past of couple days, it just got to a point where I was more or less confident in the features :) \$\endgroup\$
    – Conor O'Brien
    Dec 2, 2022 at 20:04
1
\$\begingroup\$

C (gcc), 84 83 bytes

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!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
+100
\$\begingroup\$

Pip Classic, 35 18 bytes

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

Try it online!

A lot of bytes saved thanks to @DLosc!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ DSO seems to be working at the moment. Also, the global variable o is initialized at 1, so you can take out x:1 and replace all the x's with o's for -3 bytes. If you switch to modern Pip, you can also replace x-1 with Do (keeping in mind the previous golf) for -1 bytes. \$\endgroup\$
    – Aiden Chow
    Dec 5, 2022 at 16:39
1
\$\begingroup\$

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

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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)
    }
  }
}
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 71 \$\endgroup\$
    – naffetS
    May 21 at 0:22
1
\$\begingroup\$

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
Improve this answer
\$\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.