Berechnen Sie die niedrigste Zahl, bei der die Summe der Zahlenfolgen einen bestimmten Wert überschreitet

14

Vorausgesetzt, Sie haben eine unendliche Folge von Zahlen wie folgt definiert:

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

Die Folge ist die Summe der Teiler von n, einschließlich 1 und n.

xBerechnen Sie bei einer positiven Ganzzahl als Eingabe die niedrigste Zahl, ndie ein Ergebnis größer als ergibtx .

Testfälle

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

Erwartete Ausgabe

Ihr Programm sollte beides n und die Summe seiner Teiler zurückgeben, wie folgt:

$ ./challenge 100
48,124

Regeln

Dies ist Code-Golf, so dass der kürzeste Code in Bytes in jeder Sprache gewinnt.

code-golf math StudleyJr
quelle
3
Ist diese Folge nur die Summe der ns-Teiler? Sie werden das wahrscheinlich explizit angeben wollen.
Martin Ender
3
Gemessen an Ihrer "erwarteten Leistung" möchten Sie auch beides n und f(n) , aber Sie sagen es nirgendwo in der Spezifikation.
Martin Ender
2
Boni sind schlecht , besonders wenn sie vage sind. Ich habe mich entschlossen, es zu entfernen, um dies vor Abstimmungen zu schützen.
Mr. Xcoder
2
Könnten Sie es noch einmal überprüfen f(1000) = 48? Die Divisorsumme von 48is124
caird coinheringaahing
3
Warten Sie mindestens eine Woche, bevor Sie eine Antwort annehmen, da Sie sonst von neuen Lösungen abraten können.
Zgarb

Antworten:

8

Brachylog , 9 Bytes

∧;S?hf+S>

Dieses Programm nimmt Eingaben von der "Ausgangsvariablen" .und gibt sie an die "Eingangsvariable" aus.? . Probieren Sie es online!

Erläuterung

∧;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.

Die implizite Variable Nwird in aufsteigender Reihenfolge aufgelistet, sodass der niedrigste zulässige Wert für die Ausgabe verwendet wird.

Zgarb
quelle
10

Jelly , 18 12 11 10 Bytes

1Æs>¥#ḢṄÆs

Probieren Sie es online!

-1 Byte danke an Herrn Xcoder !

Wie es funktioniert

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
quelle
Können Sie erklären, warum das 1notwendig ist und wie es sich ¥verhält?
Dylnan
1
@dylnan Das 1sagt #aus 1 Zählen zu beginnen und der ¥nimmt die vorherigen zwei Verbindungen ( Æsund >) und wendet sich als Dyade (dh mit zwei Argumenten), wobei das linke Argument der Iteration zu sein, und das rechte Argument des Eingang ist.
Caird Coinheringaahing
Oh, das macht jetzt Sinn. #war mir schon mal ein bisschen verwirrt gewesen.
Dylnan
4

Wolfram Language (Mathematica) , 53 Byte

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

Probieren Sie es online!

Versucht alle Werte zwischen 2 und x + 1, wobei x die Eingabe ist.

(Das Selectgibt eine Liste aller Werte zurück, die funktionieren, aber die Funktion {#,f@#}&nimmt all diese als Eingaben und ignoriert dann alle Eingaben außer der ersten.)

Mischa Lawrow
quelle
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))}

Probieren Sie es online!

duckmayr
quelle
59 Bytes, aber es wird für große Stapelüberlauf x.
Giuseppe
4

Schale , 12 11 Bytes

§eVḟ>⁰moΣḊN

-1 Byte, danke an @Zgarb!

Probieren Sie es online!

ბიმო
quelle
Klug! Seltsam, wie ,geht das nicht (oder dauert die Inferenz zu lange?).
2.
Es leitet einen Typ ab, gibt jedoch eine unendliche Liste aus. Dies kann durch die Überladung von ḟ verursacht werden, bei der eine ganze Zahl als zweites Argument verwendet wird, dies ist jedoch nur eine Vermutung.
Zgarb
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
quelle
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
quelle
1
Welcome to the site!
caird coinheringaahing
Some whitespace can be removed to save a few bytes. Try it online!
Steadybox
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
@NikoNyrh nice to meet a fellow clojurist, i'll edit this post soon
Alonoaky
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
quelle
3
Lambdas are certainly allowed.
Giuseppe
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>
Expand snippet

Edit: Saved 3 bytes thanks to @Arnauld.

Neil
quelle
I get "Script error." when inputting a value over 545
StudleyJr
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
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
quelle
2

APL (Dyalog), 32 bytes

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

Try it online!

⍵o⍺⍵.

Uriel
quelle
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
quelle
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
quelle
Suggest i=s=!++n instead of ++n,i=s=0
ceilingcat
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
quelle
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
quelle
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!

ბიმო
quelle
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.
quelle
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
quelle
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
@JonathanFrech: Excellent comment. Thanks for your patience with noobies in general and noob in particular ;)
Eric Duminil
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
quelle
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
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
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
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
@MichaelBoger Well, you can call an anonymous function in Python; lambda expressions do not have to be assigned to a variable.
Jonathan Frech
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
quelle
77 bytes.
Jonathan Frech
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
1

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

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

Try it online!

Output format:

sum-n

Xcali
quelle
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
quelle
0

PHP, 69 bytes

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