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

14

2

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.

StudleyJr

Posted 2017-12-02T18:29:48.123

Reputation: 285

4Is that sequence just the sum of ns divisors? You'll probably want to state that explicitly. – Martin Ender – 2017-12-02T18:31:10.760

3Also, judging by your "expected output" you want both n and f(n), but you don't say so anywhere in the specification. – Martin Ender – 2017-12-02T18:32:22.370

@MartinEnder Thanks, hopefully its clearer now. – StudleyJr – 2017-12-02T18:38:41.990

IS f(1,000) supposed to mean f(1000)? Is so, please remove the commas as it makes it harder to understand – caird coinheringaahing – 2017-12-02T18:39:51.987

2Bonuses are bad, especially when they are vague. I decided to remove it, in order to protect this from being downvoted. – Mr. Xcoder – 2017-12-02T18:42:29.310

2Could you recheck f(1000) = 48? The divisor sum of 48 is 124 – caird coinheringaahing – 2017-12-02T18:49:00.493

Oops, everything is multiplied by 10 (my bad), will edit now – StudleyJr – 2017-12-02T18:51:05.747

1Could you update to mention the expected output earlier in the spec. As it's not mentioned until after the test cases, some, like me, may miss it and just output n. – Shaggy – 2017-12-02T19:32:08.853

Would it be acceptable to include the original value of x with our output? – Shaggy – 2017-12-02T19:36:25.990

1Can the outputs be in reverse order, i.e. 124,48? – Zgarb – 2017-12-02T20:38:56.150

2Can you check f(500000)? I believe the 126000th number in the sequence is 502944. – duckmayr – 2017-12-02T20:54:53.763

Same as @duckmayr, I get f(500000) = 126000, 502944. – fede s. – 2017-12-02T22:46:01.803

Ah it should be f(5,000,000), not f(500,000). It's missing a 0. @duckmayr – fede s. – 2017-12-02T22:47:12.863

3It's good to wait at least a week before accepting an answer, otherwise you might discourage new solutions. – Zgarb – 2017-12-03T14:31:12.947

Answers

8

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.

Zgarb

Posted 2017-12-02T18:29:48.123

Reputation: 39 083

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

caird coinheringaahing

Posted 2017-12-02T18:29:48.123

Reputation: 13 702

Could you explain why the 1 is necessary and how the ¥ acts? – dylnan – 2017-12-03T22:54:37.460

1@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. – caird coinheringaahing – 2017-12-03T23:27:01.147

Oh, that makes sense now. # had been a bit confusing to me before in some cases. – dylnan – 2017-12-04T04:45:13.483

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.

Shaggy

Posted 2017-12-02T18:29:48.123

Reputation: 24 623

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

Misha Lavrov

Posted 2017-12-02T18:29:48.123

Reputation: 4 846

4

Husk, 12 11 bytes

§eVḟ>⁰moΣḊN

-1 byte, thanks to @Zgarb!

Try it online!

ბიმო

Posted 2017-12-02T18:29:48.123

Reputation: 15 345

Clever! Weird though how , doesn't work (or inference takes too long?). – ბიმო – 2017-12-02T21:28:16.173

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. – Zgarb – 2017-12-02T21:31:20.140

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.

Giuseppe

Posted 2017-12-02T18:29:48.123

Reputation: 21 077

71 bytes https://codegolf.stackexchange.com/a/149747/76266

– duckmayr – 2017-12-02T21:07:17.770

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!

duckmayr

Posted 2017-12-02T18:29:48.123

Reputation: 441

59 bytes but it will stack overflow for large x. – Giuseppe – 2017-12-03T00:17:56.373

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!

Alonoaky

Posted 2017-12-02T18:29:48.123

Reputation: 51

1Welcome to the site! – caird coinheringaahing – 2017-12-03T15:31:18.110

Some whitespace can be removed to save a few bytes. Try it online!

– Steadybox – 2018-01-14T23:27:33.770

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. – NikoNyrh – 2018-01-17T09:34:36.340

@NikoNyrh nice to meet a fellow clojurist, i'll edit this post soon – Alonoaky – 2018-01-17T11:30:52.877

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.

Mr. Xcoder

Posted 2017-12-02T18:29:48.123

Reputation: 39 774

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.

Neil

Posted 2017-12-02T18:29:48.123

Reputation: 95 035

I get "Script error." when inputting a value over 545 – StudleyJr – 2017-12-04T16:53:41.177

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".) – Neil – 2017-12-04T16:59:46.697

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

Unihedron

Posted 2017-12-02T18:29:48.123

Reputation: 1 115

3Lambdas are certainly allowed. – Giuseppe – 2017-12-03T00:32:56.210

2

APL (Dyalog), 32 bytes

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

Try it online!

⍵o⍺⍵.

Uriel

Posted 2017-12-02T18:29:48.123

Reputation: 11 708

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!

Steadybox

Posted 2017-12-02T18:29:48.123

Reputation: 15 798

Suggest i=s=!++n instead of ++n,i=s=0 – ceilingcat – 2019-11-09T02:11:26.360

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

dzaima

Posted 2017-12-02T18:29:48.123

Reputation: 19 048

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)

Luis Mendo

Posted 2017-12-02T18:29:48.123

Reputation: 87 464

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.

Mr. Xcoder

Posted 2017-12-02T18:29:48.123

Reputation: 39 774

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!

ბიმო

Posted 2017-12-02T18:29:48.123

Reputation: 15 345

2

Ohm v2, 11 bytes

£^DVΣD³>‽;«

Try it online!

Cinaski

Posted 2017-12-02T18:29:48.123

Reputation: 1 588

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

noob

Posted 2017-12-02T18:29:48.123

Reputation: 21

3

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

– Jonathan Frech – 2017-12-02T23:46:12.937

@JonathanFrech: Excellent comment. Thanks for your patience with noobies in general and noob in particular ;) – Eric Duminil – 2017-12-03T14:04:08.147

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 ;

fede s.

Posted 2017-12-02T18:29:48.123

Reputation: 945

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.

Michael Boger

Posted 2017-12-02T18:29:48.123

Reputation: 323

1

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!

– caird coinheringaahing – 2017-12-03T21:59:01.570

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. – Michael Boger – 2017-12-03T22:02:54.423

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!

– caird coinheringaahing – 2017-12-03T22:05:22.730

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. – Michael Boger – 2017-12-04T15:32:52.607

@MichaelBoger Well, you can call an anonymous function in Python; lambda expressions do not have to be assigned to a variable.

– Jonathan Frech – 2017-12-04T16:10:40.097

@JonathanFrech I personally feel that should require counting the print statement as part of the code because otherwise it doesn't output anything and cannot be called subsequently to output anything -- but I realize this is not the community standard, so I'll have to get used to it. – Michael Boger – 2017-12-05T16:38:50.930

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!

Chas Brown

Posted 2017-12-02T18:29:48.123

Reputation: 8 959

77 bytes. – Jonathan Frech – 2017-12-04T16:14:17.017

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. – Michael Boger – 2018-07-15T07:05:19.097

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)

Bernat

Posted 2017-12-02T18:29:48.123

Reputation: 181

89 bytes – ceilingcat – 2019-11-09T02:07:13.657

1

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

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

Try it online!

Output format:

sum-n

Xcali

Posted 2017-12-02T18:29:48.123

Reputation: 7 671

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

NikoNyrh

Posted 2017-12-02T18:29:48.123

Reputation: 2 361

0

PHP, 69 bytes

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

chocochaos

Posted 2017-12-02T18:29:48.123

Reputation: 547

0

Perl 6, 48 bytes

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

Try it online!

Sean

Posted 2017-12-02T18:29:48.123

Reputation: 4 136

Asked: 2017-12-02T18:29:48.123

Viewed: 1 602 times

Active: 2018-01-17T20:18:49.087