Вычислить наименьшее число, где сумма последовательности чисел превышает заданное значение

14

Учитывая, что у вас есть бесконечная последовательность чисел, определенная следующим образом:

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

Последовательность представляет собой сумму делителей n, включая 1 и n.

Учитывая положительное целое число в xкачестве входных данных, рассчитайте наименьшее число, nкоторое даст результат больше, чем x.

Контрольные примеры

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

Ожидаемый результат

Ваша программа должна возвращать как n и сумму его делителей, например так:

$ ./challenge 100
48,124

правила

Это код-гольф, поэтому выигрывает самый короткий код в байтах на каждом языке.

code-golf math StudleyJr
источник
4
Является ли эта последовательность просто суммой ns делителей? Вы, вероятно, захотите заявить об этом явно.
Мартин Эндер
3
Кроме того, судя по вашему «ожидаемому результату», вы хотите и то n и другое f(n), но вы нигде не говорите об этом в спецификации.
Мартин Эндер
2
Бонусы плохие , особенно когда они расплывчаты. Я решил удалить это, чтобы защитить это от понижения голоса.
г-н Xcoder
2
Не могли бы вы перепроверить f(1000) = 48? Делитель сумма 48составляет124
Кэрд coinheringaahing
3
Хорошо подождать хотя бы неделю, прежде чем принять ответ, иначе вы можете отговорить от новых решений.
Згарб

Ответы:

8

Брахилог , 9 байт

∧;S?hf+S>

Эта программа принимает входные данные из «выходной переменной» .и выводит их во «входную переменную» ?. Попробуйте онлайн!

объяснение

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

Неявная переменная Nперечисляется в порядке возрастания, поэтому для вывода используется ее наименьшее допустимое значение.

Zgarb
источник
10

Желе , 18 12 11 10 байт

1Æs>¥#ḢṄÆs

Попробуйте онлайн!

-1 байт благодаря мистеру Xcoder !

Как это устроено

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
Кэрд
источник
Не могли бы вы объяснить, почему 1это необходимо и как ¥действует?
Дилнан
1
@dylnan 1говорит , #чтобы начать отсчет с 1 и ¥принимает предыдущие две ссылки ( Æsи >) , и применяет их в качестве диады (т.е. с двумя аргументами), с левым аргументом является итерация, а правый аргумент является вход.
caird coinheringaahing
О, это имеет смысл сейчас. #в некоторых случаях меня это немного смущало.
Дилнан
4

Wolfram Language (Mathematica) , 53 байта

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

Попробуйте онлайн!

Пытается использовать все значения от 2 до x + 1, где x - это ввод.

( SelectВозвращает список всех значений, которые работают, но функция {#,f@#}&принимает все это как входные данные, а затем игнорирует все свои входные данные, кроме первого.)

Миша лавров
источник
4

Шелуха , 12 11 байт

§eVḟ>⁰moΣḊN

-1 байт, спасибо @Zgarb!

Попробуйте онлайн!

ბიმო
источник
Умная! Странно, однако, как ,не работает (или вывод занимает слишком много времени?).
მოიმო
Он выводит тип, но выводит бесконечный список. Это может быть вызвано перегрузкой ḟ, которая принимает целое число в качестве второго аргумента, но это только предположение.
Згарб
4

Japt , 15 байт

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

Попытайся

объяснение

Неявный ввод целого числа U. []наша оболочка массива Для первого элемента @ }a- это функция, которая работает непрерывно, пока не вернет истинное значение, каждый раз передавая себе возрастающее целое число (начиная с 0), и выводя окончательное значение этого целого числа. âполучает делители текущего целого числа ( X), xсуммирует их, и этот результат присваивается переменной V. <проверяет, если Uменьше V. Второй элемент в массиве тогда просто V.

мохнатый
источник
4

Clojure , 127 байт

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

Попробуйте онлайн!

спасибо @steadybox за -4 байта!

Alonoaky
источник
1
Добро пожаловать на сайт!
caird coinheringaahing
Некоторые пробелы могут быть удалены, чтобы сохранить несколько байтов. Попробуйте онлайн!
Steadybox
В этом случае reduceможет быть заменено на apply, также функция eможет быть выражена как анонимная функция через #(...)синтаксис, вам не нужно называть ее в Code Golf. #(=(rem n %)0)короче чем #(zero?(rem n %)). И помните, что ,это пробел, и в этом случае его можно удалить, так как за ним следует (, так что он будет проанализирован правильно.
NikoNyrh
@NikoNyrh приятно познакомиться с коллегой-клоюристом, я скоро отредактирую этот пост
Alonoaky
3

Рубин , 58 байт

Полная программа, потому что я не уверен, разрешены ли лямбды. / пожимание плечами

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

Попробуйте онлайн!

объяснение

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
источник
3
Лямбды конечно разрешены.
Джузеппе
3

JavaScript (ES6), 61 58 байт

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>
Развернуть фрагмент

Изменить: Сохранено 3 байта благодаря @Arnauld.

Нил
источник
Я получаю «Ошибка сценария». при вводе значения более 545
StudleyJr
Попробуйте использовать Safari; по-видимому, он поддерживает Tail Call Optimization. (Или, если вы можете их найти, некоторые версии Chrome включают его через «Экспериментальные функции JavaScript».)
Нил
2

SOGL V0.12 , 14 байт

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

Попробуй здесь!

Объяснение:

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
источник
2

MATL , 12 байт

`@Z\sG>~}@6M

Попробуйте онлайн!

объяснение

`      % 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)
Луис Мендо
источник
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.
источник
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
источник
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
источник
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
источник
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
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
источник
0

PHP, 69 bytes

for(;$argv[1]>=$t;)for($t=$j=++$i;--$j;)$t+=$i%$j?0:$j;echo$i,',',$t;
chocochaos
источник