Calculate the lowest number where the sum of the sequence of numbers exceeds a given value

Question

Given you have an infinite sequence of numbers defined as follows:

1: 1 = 1
2: 1 + 2 = 3
3: 1 + 3 = 4
4: 1 + 2 + 4 = 7
5: 1 + 5 = 6
6: 1 + 2 + 3 + 6 = 12
7: 1 + 7 = 8
...

The sequence is the sum of the divisors of n, including 1 and n.

Given a positive integer x as input, calculate the lowest number n which will produce a result greater than x.

Test cases

f(100) = 48, ∑ = 124
f(25000) = 7200, ∑ = 25389
f(5000000) = 1164240, ∑ = 5088960

Expected Output

Your program should return both n and the sum of its divisors, like so:

$ ./challenge 100
48,124

Rules

This is code-golf so the shortest code in bytes, in each language wins.

Is that sequence just the sum of ns divisors? You'll probably want to state that explicitly. — Martin Ender, Commented Dec 2, 2017 at 18:31
Also, judging by your "expected output" you want both n and f(n), but you don't say so anywhere in the specification. — Martin Ender, Commented Dec 2, 2017 at 18:32
Bonuses are bad, especially when they are vague. I decided to remove it, in order to protect this from being downvoted. — Mr. Xcoder, Commented Dec 2, 2017 at 18:42
Could you recheck f(1000) = 48? The divisor sum of 48 is 124 — caird coinheringaahin g, Commented Dec 2, 2017 at 18:49
It's good to wait at least a week before accepting an answer, otherwise you might discourage new solutions. — Zgarb, Commented Dec 3, 2017 at 14:31

caird coinheringaahin g · Accepted Answer · 2017-12-03 14:55:53Z

10

Jelly, 18 12 11 10 bytes

1Æs>¥#ḢṄÆs

Try it online!

-1 byte thanks to Mr. Xcoder!

How it works

1Æs>¥#ḢṄÆs - Main link. Argument: n (integer)
1   ¥#     - Find the first n integers where...
 Æs        -   the divisor sum
   >       -   is greater than the input
       Ṅ   - Print...
      Ḣ    -   the first element
        Æs - then print the divisor sum

edited Dec 3, 2017 at 14:55

answered Dec 2, 2017 at 18:52

caird coinheringaahin g♦

50.1k11 gold badges126 silver badges353 bronze badges

\$\begingroup\$ Could you explain why the 1 is necessary and how the ¥ acts? \$\endgroup\$
– dylnan
Commented Dec 3, 2017 at 22:54
1

\$\begingroup\$ @dylnan The 1 tells # to start counting from 1 and the ¥ takes the previous two links (Æs and >) and applies them as a dyad (i.e. with two arguments), with the left argument being the iteration, and the right argument being the input. \$\endgroup\$
– caird coinheringaahin g ♦
Commented Dec 3, 2017 at 23:27
\$\begingroup\$ Oh, that makes sense now. # had been a bit confusing to me before in some cases. \$\endgroup\$
– dylnan
Commented Dec 4, 2017 at 4:45

Add a comment |

Zgarb · Accepted Answer · 2017-12-02 21:46:05Z

Brachylog, 9 bytes

∧;S?hf+S>

This program takes input from the "output variable" ., and outputs to the "input variable" ?. Try it online!

Explanation

∧;S?hf+S>
∧;S        There is a pair [N,S]
   ?       which equals the output
    h      such that its first element's
     f     factors'
      +    sum
       S   equals S,
        >  and is greater than the input.

The implicit variable N is enumerated in increasing order, so its lowest legal value is used for the output.

Misha Lavrov · Accepted Answer · 2017-12-02 20:20:16Z

4

Wolfram Language (Mathematica), 53 bytes

{#,f@#}&@@Select[Range[x=#]+1,(f=Tr@*Divisors)@#>x&]&

Try it online!

Tries all values between 2 and x+1, where x is the input.

(The Select returns a list of all values that work, but the function {#,f@#}& takes all of these as inputs, and then ignores all its inputs but the first.)

edited Dec 2, 2017 at 20:20

answered Dec 2, 2017 at 20:14

Misha Lavrov

5,26512 silver badges27 bronze badges

Add a comment |

duckmayr · Accepted Answer · 2017-12-02 20:59:00Z

4

R, 71 bytes

function(x)for(n in 1:x){z=sum(which(n%%1:n==0));if(z>x)return(c(n,z))}

Try it online!

answered Dec 2, 2017 at 20:59

duckmayr

4513 silver badges6 bronze badges

\$\begingroup\$ 59 bytes but it will stack overflow for large x. \$\endgroup\$
– Giuseppe
Commented Dec 3, 2017 at 0:17

Add a comment |

ბიმო · Accepted Answer · 2017-12-02 21:27:03Z

4

Husk, 12 11 bytes

§eVḟ>⁰moΣḊN

-1 byte, thanks to @Zgarb!

Try it online!

edited Dec 2, 2017 at 21:27

answered Dec 2, 2017 at 20:15

ბიმო

16.9k2 gold badges41 silver badges104 bronze badges

\$\begingroup\$ Clever! Weird though how , doesn't work (or inference takes too long?). \$\endgroup\$
– ბიმო
Commented Dec 2, 2017 at 21:28
\$\begingroup\$ It does infer a type, but outputs an infinite list. It may be caused by the overloading of ḟ that takes an integer as the second argument, but that's just a guess. \$\endgroup\$
– Zgarb
Commented Dec 2, 2017 at 21:31

Add a comment |

Giuseppe · Accepted Answer · 2017-12-04 16:50:45Z

4

R, 73 bytes

n=scan();while(1){d=(x=1:T)[!T%%x];if(sum(d)>n)break;T=T+1};cat(T,sum(d))

Try it online!

Outgolfed by duckmayr.

edited Dec 4, 2017 at 16:50

answered Dec 2, 2017 at 20:31

Giuseppe

28.8k3 gold badges31 silver badges104 bronze badges

\$\begingroup\$ 71 bytes codegolf.stackexchange.com/a/149747/76266 \$\endgroup\$
– duckmayr
Commented Dec 2, 2017 at 21:07

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

Japt, 15 bytes

[@<(V=Xâ x}a V]

Try it

Explanation

Implicit input of integer U. [] is our array wrapper. For the first element, @ }a is a function that run continuously until it returns a truthy value, passing itself an incrementing integer (starting at 0) each time, and outputting the final value of that integer. â gets the divisors of the current integer (X), x sums them and that result is assigned to variable V. < checks if U is less than V. The second element in the array is then just V.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 2, 2017 at 19:20

Shaggy

42.7k4 gold badges36 silver badges94 bronze badges

Add a comment |

Alonoaky · Accepted Answer · 2018-01-17 09:16:47Z

4

Clojure, 127 bytes

(defn f[n](reduce +(filter #(zero?(rem n %))(range 1(inc n)))))
(defn e[n](loop[i 1 n n](if(>(f i)n){i,(f i)}(recur(inc i)n))))

Try it online!

thanks to @steadybox for -4 bytes!

edited Jan 17, 2018 at 9:16

answered Dec 3, 2017 at 15:11

Alonoaky

512 bronze badges

1

\$\begingroup\$ Welcome to the site! \$\endgroup\$
– caird coinheringaahin g ♦
Commented Dec 3, 2017 at 15:31
\$\begingroup\$ Some whitespace can be removed to save a few bytes. Try it online! \$\endgroup\$
– Steadybox
Commented Jan 14, 2018 at 23:27
\$\begingroup\$ In this case reduce can be replaced by apply, also the function e could be expressed as an anonymous function via the #(...) syntax, you don't need to name it at Code Golf. #(=(rem n %)0) is shorter than #(zero?(rem n %)). And remember that , is whitespace, and can be removed in this case as it is followed by (, so it will be parsed correctly. \$\endgroup\$
– NikoNyrh
Commented Jan 17, 2018 at 9:34
\$\begingroup\$ @NikoNyrh nice to meet a fellow clojurist, i'll edit this post soon \$\endgroup\$
– Alonoaky
Commented Jan 17, 2018 at 11:30

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

Ruby, 58 bytes

Full program because I'm not sure if lambdas are allowed. /shrug

gets
$.+=1until$_.to_i.<v=(1..$.).sum{|n|$.%n<1?n:0}
p$.,v

Try it online!

Explanation

gets     # read line ($_ is used instead of v= because it cuts a space)
$.+=1    # $. is "lines read" variable which starts at 1 because we read 1 line
    until     # repeat as long as the next part is not true
$_.to_i  # input, as numeric
  .<v=   # is <, but invoked as function to lower operator prescedence
  (1..$.)        # Range of 1 to n
  .sum{|n|       # .sum maps values into new ones and adds them together
     $.%n<1?n:0  # Factor -> add to sum, non-factor -> 0
  }
p$.,v    # output n and sum

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 2, 2017 at 21:09

Unihedron

1,29514 silver badges21 bronze badges

3

\$\begingroup\$ Lambdas are certainly allowed. \$\endgroup\$
– Giuseppe
Commented Dec 3, 2017 at 0:32

Add a comment |

Neil · Accepted Answer · 2017-12-03 01:11:22Z

3

JavaScript (ES6), 61 58 bytes

f=(n,i=1,s=j=0)=>j++<i?f(n,i,i%j?s:s+j):s>n?[i,s]:f(n,++i)

<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Edit: Saved 3 bytes thanks to @Arnauld.

edited Dec 3, 2017 at 1:11

answered Dec 2, 2017 at 20:33

Neil

174k12 gold badges73 silver badges277 bronze badges

\$\begingroup\$ I get "Script error." when inputting a value over 545 \$\endgroup\$
– StudleyJr
Commented Dec 4, 2017 at 16:53
\$\begingroup\$ Try using Safari; apparently it supports Tail Call Optimisation. (Or if you can find them, some versions of Chrome enable it via the "Experimental JavaScript features".) \$\endgroup\$
– Neil
Commented Dec 4, 2017 at 16:59

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-12-03 10:00:17Z

3

05AB1E, 11 bytes

>LʒÑO‹}нDÑO

Try it online!

Leaves the output on the stack, as allowed per meta consensus. I added ) for the sake of visualization, but the program also implicitly prints the top of the stack.

edited Dec 3, 2017 at 10:00

answered Dec 2, 2017 at 19:16

Mr. Xcoder

42.4k9 gold badges79 silver badges214 bronze badges

Add a comment |

Uriel · Accepted Answer · 2017-12-02 19:07:37Z

2

APL (Dyalog), 32 bytes

{⍺<o←+/o/⍨0=⍵|⍨o←⍳⍵:⍵,o⋄⍺∇⍵+1}∘0

Try it online!

⍵o⍺⍵.

edited Dec 2, 2017 at 19:07

answered Dec 2, 2017 at 18:52

Uriel

13.2k4 gold badges17 silver badges45 bronze badges

Add a comment |

dzaima · Accepted Answer · 2017-12-02 19:13:37Z

2

SOGL V0.12, 14 bytes

1[:Λ∑:A.>?ao←I

Try it Here!

Explanation:

1               push 1
 [              while ToS != 0
  :Λ              get the divisors
    ∑             sum
     :A           save on variable A without popping
       .>?  ←     if greater than the input
          ao        output the variable A
            ←       and stop the program, implicitly outputting ToS - the counter
             I    increment the counter

edited Dec 2, 2017 at 19:13

answered Dec 2, 2017 at 19:07

dzaima

20.3k2 gold badges41 silver badges75 bronze badges

Add a comment |

Steadybox · Accepted Answer · 2017-12-02 19:13:54Z

2

C, 79 78 bytes

i,n,s;f(x){for(i=n=s=0;x>s;s+=n%++i?0:i)i-n||(++n,i=s=0);printf("%d %d",n,s);}

Try it online!

edited Dec 2, 2017 at 19:13

answered Dec 2, 2017 at 18:56

Steadybox

16.5k5 gold badges40 silver badges84 bronze badges

\$\begingroup\$ Suggest i=s=!++n instead of ++n,i=s=0 \$\endgroup\$
– ceilingcat
Commented Nov 9, 2019 at 2:11

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

MATL, 12 bytes

`@Z\sG>~}@6M

Try it online!

Explanation

`      % Do...while
  @    %   Push iteration index (1-based)
  Z\   %   Array of divisors
  s    %   Sum of array
  G    %   Push input
  >~   %   Greater than; logical negate. This is the loop condition
}      % Finally (execute on loop exit)
  @    %   Push latest iteration index
  6M   %   Push latest sum of divisors again
       % End (implicit). Run new iteration if top of the stack is true
       % Display stack (implicit)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 2, 2017 at 19:23

Luis Mendo

105k9 gold badges133 silver badges371 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-12-02 20:08:22Z

2

Gaia, 11 bytes

dΣ@>
↑#(:dΣ

Try it online!

Leaves the output on the stack, as allowed per meta consensus. I added €. for the sake of visualization, but the program also implicitly prints the top of the stack.

edited Dec 2, 2017 at 20:08

answered Dec 2, 2017 at 20:01

Mr. Xcoder

42.4k9 gold badges79 silver badges214 bronze badges

Add a comment |

ბიმო · Accepted Answer · 2017-12-02 21:21:23Z

2

Haskell, 59 bytes

f x=[(i,s)|i<-[1..],s<-[sum[d|d<-[1..i],i`mod`d<1]],s>x]!!0

-1 byte, thanks to @nimi!

Try it online!

edited Dec 2, 2017 at 21:21

answered Dec 2, 2017 at 21:03

ბიმო

16.9k2 gold badges41 silver badges104 bronze badges

Add a comment |

Cinaski · Accepted Answer · 2017-12-02 21:26:36Z

2

Ohm v2, 11 bytes

£^DVΣD³>‽;«

Try it online!

answered Dec 2, 2017 at 21:26

Cinaski

2,2581 gold badge8 silver badges17 bronze badges

Add a comment |

fede s. · Accepted Answer · 2017-12-02 23:30:30Z

2

Factor, 88

USE: math.primes.factors [ 0 0 [ drop 1 + dup divisors sum pick over > ] loop rot drop ]

Brute-force search. It's a quotation (lambda), call it with x on the stack, leaves n and f(n) on the stack.

As a word:

: f(n)>x ( x -- n f(n) )
  0 0 [ drop 1 + dup divisors sum pick over > ] loop rot drop ;

answered Dec 2, 2017 at 23:30

fede s.

9856 silver badges10 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Python 3, 163 bytes

def f(x):
    def d(x):return[i for i in range(1,x+1) if x%i==0]
    return min(i for i in range(x) if sum(d(i)) >x),sum(d(min(i for i in range(x) if sum(d(i)) >x)))

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 2, 2017 at 22:54

noob

211 bronze badge

3

\$\begingroup\$ Hello and welcome to PPCG; nice first post! From a golfing aspect, you could save some bytes by removing whitespace, using lambda functions, collapsing everything onto one line and not repeating yourself. We also usually link to an online testing environment, like for example TIO (105 bytes, using the techniques described above.) \$\endgroup\$
– Jonathan Frech
Commented Dec 2, 2017 at 23:46
\$\begingroup\$ @JonathanFrech: Excellent comment. Thanks for your patience with noobies in general and noob in particular ;) \$\endgroup\$
– Eric Duminil
Commented Dec 3, 2017 at 14:04

Add a comment |

caird coinheringaahin g · Accepted Answer · 2017-12-03 21:59:39Z

2

Python 3, 100 bytes

d=lambda y:sum(i+1for i in range(y)if y%-~i<1)
f=lambda x:min((j,d(j))for j in range(x+1)if x<=d(j))

Try it online!

Thanks to Jonathan Frech's comment on the previous python 3 attempt, I have just greatly expanded my knowledge of python syntax. I'd never have thought of the -~i for i+1 trick, which saves two characters.

However, that answer is 1) not minimal and 2) doesn't work for x=1 (due to an off-by-one error which is easy to make while going for brevity; I suggest everyone else check their answers for this edge case!).

Quick explanation: sum(i+1for i in range(y)if y%-~i<1) is equivalent to sum(i for i in range(1,y+1)if y%i<1) but saves two characters. Thanks again to Mr. Frech.

d=lambda y:sum(i+1for i in range(y)if y%-~i<1) therefore returns the divisors of y.

f=lambda x:min((j,d(j))for j in range(x+1)if x<=d(j)) is where I really did work. Since comparing a tuple works in dictionary order, we can compare j,d(j) as easily as we can compare j, and this lets us not have to find the minimal j, store it in a variable, and /then/ compute the tuple in a separate operation. Also, we have to have the <=, not <, in x<=d(j), because d(1) is 1 so if x is 1 you get nothing. This is also why we need range(x+1) and not range(x).

I'd previously had d return the tuple, but then I have to subscript it in f, so that takes three more characters.

edited Dec 3, 2017 at 21:59

caird coinheringaahin g♦

50.1k11 gold badges126 silver badges353 bronze badges

answered Dec 3, 2017 at 21:49

Sam Howard

3432 silver badges8 bronze badges

1

\$\begingroup\$ Welcome to the site and nice first post. You can get to 98 bytes by removing the f= as anonymous functions are perfectly acceptable here! \$\endgroup\$
– caird coinheringaahin g ♦
Commented Dec 3, 2017 at 21:59
\$\begingroup\$ You can't call an anonymous function from another line of code, is the problem -- I have a separate print(f(100)) statement to test that the function works. \$\endgroup\$
– Sam Howard
Commented Dec 3, 2017 at 22:02
\$\begingroup\$ That's not a problem here. It's perfectly acceptable and works to not include the f= in your byte count, and is a good way to golf in Python. Check this for more golfing tips in Python! \$\endgroup\$
– caird coinheringaahin g ♦
Commented Dec 3, 2017 at 22:05
\$\begingroup\$ Hm. I can equal, but not better, my submission by appending q=range and replacing range with q in both existing instances. Sadly, this doesn't improve it and since lambda is a keyword I can't use it for that, I'd have to do exec() tricks wasting too many characters. \$\endgroup\$
– Sam Howard
Commented Dec 4, 2017 at 15:32
\$\begingroup\$ @MichaelBoger Well, you can call an anonymous function in Python; lambda expressions do not have to be assigned to a variable. \$\endgroup\$
– Jonathan Frech
Commented Dec 4, 2017 at 16:10

| Show 1 more comment

Chas Brown · Accepted Answer · 2017-12-04 08:52:15Z

2

Python 2, 81 bytes

def f(n):
 a=b=0
 while b<n:
	a+=1;i=b=0
	while i<a:i+=1;b+=i*(a%i<1)
 return a,b

Try it online!

answered Dec 4, 2017 at 8:52

Chas Brown

9,7671 gold badge13 silver badges39 bronze badges

\$\begingroup\$ 77 bytes. \$\endgroup\$
– Jonathan Frech
Commented Dec 4, 2017 at 16:14
\$\begingroup\$ Replacing the tabs with two spaces makes this work in python 3 at 83 bytes, although to try it I had to put parentheses in the print statement. You can also replace the return statement with a print statement and not need an auxiliary function to print it; the bytes stay the same. \$\endgroup\$
– Sam Howard
Commented Jul 15, 2018 at 7:05

Add a comment |

Bernat · Accepted Answer · 2017-12-05 22:13:22Z

1

Java (OpenJDK 8), 91 bytes

i->{for(int j=0;j++<i;)for(int k=0,l=0;k++<j;)if((l+=j%k<1?k:0)>i)return k+","+l;return"";}

Try it online! (timeout on third test case)

edited Dec 5, 2017 at 22:13

answered Dec 5, 2017 at 13:04

Bernat

1811 silver badge5 bronze badges

\$\begingroup\$ 89 bytes \$\endgroup\$
– ceilingcat
Commented Nov 9, 2019 at 2:07

Add a comment |

Xcali · Accepted Answer · 2017-12-05 23:15:30Z

1

Perl 5, 60 + 1 (`-p`) = 61 bytes

$"=$_;until($_>$"){$_=$/=0;$\--;$_+=$\%$/?0:$/until++$/>-$\}

Try it online!

Output format:

sum-n

answered Dec 5, 2017 at 23:15

Xcali

15.7k2 gold badges15 silver badges39 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2018-01-17 09:40:18Z

0

Clojure, 102 bytes

#(loop[i 1](let[s(apply +(for[j(range 1(inc i)):when(=(mod i j)0)]j))](if(> s %)[i s](recur(inc i)))))

answered Jan 17, 2018 at 9:40

NikoNyrh

2,6819 silver badges8 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

PHP, 69 bytes

for(;$argv[1]>=$t;)for($t=$j=++$i;--$j;)$t+=$i%$j?0:$j;echo$i,',',$t;

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 17, 2018 at 17:03

chocochaos

5472 silver badges11 bronze badges

Add a comment |

Sean · Accepted Answer · 2018-01-17 20:18:49Z

0

Perl 6, 48 bytes

{first :kv,*>$_,map {sum grep $_%%*,1..$_},0..*}

Try it online!

answered Jan 17, 2018 at 20:18

Sean

7,98611 silver badges15 bronze badges

Add a comment |

Stack Exchange Network

Calculate the lowest number where the sum of the sequence of numbers exceeds a given value

27 Answers 27

Jelly, 18 12 11 10 bytes

How it works

Brachylog, 9 bytes

Explanation

Wolfram Language (Mathematica), 53 bytes

R, 71 bytes

Husk, 12 11 bytes

R, 73 bytes

Japt, 15 bytes

Explanation

Clojure, 127 bytes

Ruby, 58 bytes

Explanation

JavaScript (ES6), 61 58 bytes

05AB1E, 11 bytes

APL (Dyalog), 32 bytes

SOGL V0.12, 14 bytes

C, 79 78 bytes

MATL, 12 bytes

Explanation

Gaia, 11 bytes

Haskell, 59 bytes

Ohm v2, 11 bytes

Factor, 88

Python 3, 163 bytes

Python 3, 100 bytes

Python 2, 81 bytes

Java (OpenJDK 8), 91 bytes

Perl 5, 60 + 1 (`-p`) = 61 bytes

Clojure, 102 bytes

PHP, 69 bytes

Perl 6, 48 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
number-theory
or ask your own question.

Linked

Hot Network Questions

Calculate the lowest number where the sum of the sequence of numbers exceeds a given value

27 Answers 27

Jelly, 18 12 11 10 bytes

How it works

Brachylog, 9 bytes

Explanation

Wolfram Language (Mathematica), 53 bytes

R, 71 bytes

Husk, 12 11 bytes

R, 73 bytes

Japt, 15 bytes

Explanation

Clojure, 127 bytes

Ruby, 58 bytes

Explanation

JavaScript (ES6), 61 58 bytes

05AB1E, 11 bytes

APL (Dyalog), 32 bytes

SOGL V0.12, 14 bytes

C, 79 78 bytes

MATL, 12 bytes

Explanation

Gaia, 11 bytes

Haskell, 59 bytes

Ohm v2, 11 bytes

Factor, 88

Python 3, 163 bytes

Python 3, 100 bytes

Python 2, 81 bytes

Java (OpenJDK 8), 91 bytes

Perl 5, 60 + 1 (-p) = 61 bytes

Clojure, 102 bytes

PHP, 69 bytes

Perl 6, 48 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Perl 5, 60 + 1 (`-p`) = 61 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
number-theory
or ask your own question.