Найдите наибольшее количество различных целых чисел, которые суммируются с n

18

Задание

Учитывая входное положительное целое число n(от 1 до ограничения вашего языка включительно), верните или выведите максимальное количество различных положительных целых чисел, которые суммируются n.

Тестовые случаи

Давайте fопределим действительную функцию согласно задаче:

Последовательность для f, начиная с 1:

1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...

Как большой тестовый пример:

>>> f(1000000000) // Might not be feasible with brute-forcers
44720

Тестовый код

Для любых тестовых случаев, не указанных явно, вывод вашего кода должен соответствовать результату следующего:

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
    }
}

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

Аддисон Крамп
источник
Это может быть 0-проиндексировано?
полностью человек
1
@totallyhuman "это" быть ответами? Потому что речь идет не о списке ...
Аддисон Крамп
3
@totallyhuman Нет. Это касается отдельных разделов конкретных чисел.
Аддисон Крамп
5
Это OEIS A003056 .
Джепп Стиг Нильсен
4
Я чувствую себя незначительным почти каждый раз, когда вхожу в стек Codegolf. Ответы и комментарии гораздо более чем унизительны. Вопросы, как правило, тоже интересны, но с его комментарием @JeppeStigNielsen просто добавляет готовые чертежи, когда мы все еще обдумываем площадь.
KalleMP

Ответы:

9

05AB1E , 4 байта

ÅTg<

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

Идеальный инструмент для работы.

ÅTдает перечень Å будет T riangular числа до и включая N ( к сожалению , включает в себя-тоже, в противном случае было бы 3 байта), g<получает Len г - й и уменьшает его.

Мистер Xcoder
источник
8

Желе , 6 5 байт

R+\»ċ

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

Несколько эффективнее. Эта последовательность увеличивается на треугольные числа, поэтому она просто подсчитывает, сколько треугольных чисел меньше n .

Объяснение:

        # Main link
R       # Range, generate [1..n]
 +\     # Cumulative sum (returns the first n triangular numbers)
   »    # For each element, return the maximum of that element and 'n'
    ċ   # How many elements are 'n'? (implicit right argument is n)
DJMcMayhem
источник
В объяснении вы наверняка имеете в виду «сколько чисел меньше или равно n »
Луис Мендо
@LuisMendo Смотрите новое объяснение.
DJMcMayhem
6

Haskell , 26 байтов

-2 байта благодаря H.PWiz.

(!!)$do x<-[0..];x<$[0..x]

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

Это возвращает n-й элемент целых чисел, где каждый i реплицируется i + 1 раз.

totallyhuman
источник
3
Я не могу не спросить, что такое "succ"
Аддисон Крамп
Да, я знаю, лол. succобозначает successor.
полностью человек
5

Brain-Flak , 36 байт

<>(())({()<(({}())){<>({}[()])}>{}})

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

При этом используется та же структура, что и в стандартном алгоритме деления, за исключением того, что «делитель» увеличивается каждый раз, когда он читается.

Nitrodon
источник
3

Brain-Flak , 82 байта

Добавлены пробелы для «читабельности»

(())

{
    {}

    ((({})[[]]))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

}{}{}{}

([]<>)

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

DJMcMayhem
источник
Соревнование как всегда
Пшеничный волшебник
1
Кто бы мог подумать, что сочетание двух нечитаемых языков, пробелов и Brain-Flak, можно считать «читабельным»!
Caird Coinheringaahing
3

R , 28 байт

function(n)rep(1:n,1:n+1)[n]

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

Создает вектор 1повторяющихся 2времен, 2повторяющихся 3времен, ..., nповторяющихся n+1времен и принимает nthэлемент. Это приведет к ошибке памяти либо из-за 1:nслишком большого размера, либо из-за слишком большого повторного списка с n*(n+1)/2 - 1элементами.

R , 29 байт

function(n)((8*n+1)^.5-1)%/%2

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

Вычисляет значение напрямую, используя формулу из ответа алефальфы . Это должно выполняться без проблем, кроме, возможно, числовой точности.

R , 30 байт

function(n)sum(cumsum(1:n)<=n)

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

Считает треугольные числа меньше или равно n. Возможно, это приведет к ошибке памяти, если она 1:nбудет достаточно большой, например, при 1e9ее выдаче Error: cannot allocate vector of size 3.7 Gb.

Giuseppe
источник
2

JavaScript (Node.js) , 18 байт

x=>(x-~x)**.5-.5|0

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

Unihedron
источник
Это всегда правильно? Я не уверен floor((sqrt(8x+4)-1)/2)(ваша формула) и floor((sqrt(8x+1)-1)/2)(правильная формула) дают одинаковый результат для каждого x.
ETHпродукция
@ETHproductions Я мог бы блефовать и говорить «да», но я думаю, что более честный ответ заключается в том, что вы должны попытаться разработать свою собственную гипотезу и выяснить, если / почему она отражает ту же формулу. Я не придумал такой подход сам (я узнал об этом с другого сайта), но я немного поиграл с ним. Это очень интересный подход, и я не хочу так рано рассекать лягушку.
Unihedron
Хм. Я не уверен, как это доказать напрямую, но я написал брутфорсер, который не находит сбоев до 100 миллионов.
ETHproductions
2

Japt , 8 байт

Закрытое формульное решение.

*8Ä ¬É z

Попытайся


объяснение

Умножьте на 8, добавьте 1 ( Ä), получите квадратный корень ( ¬), вычтите 1 ( É) и поделите результат на 2 ( z).


Альтернатива, 8 байт

Порт решения DJMcMayhem's Jelly .

õ å+ è§U

Попытайся

Создайте массив целых чисел ( õ) от 1 до input, кумулятивно уменьшите ( å) на добавление ( +) и count ( è) элементов, которые меньше или равны ( §) input ( U).

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

Brain-Flak , 70 56 48 байт

{([(({}[({}())()])[()])]<>){<>({}())}{}<>{}}<>{}

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

объяснение

Основной частью этого является следующий фрагмент, который я написал:

([(({})[()])]<>){<>({}())}{}<>{}

Это ничего не изменит, если TOS будет положительным, и переключит стеки в противном случае. Это супер стека нечисто, но это работает. Теперь основная часть программы вычитает все большие числа из входных данных, пока входные данные не являются положительными. Мы запускаем аккумулятор в 1 каждый раз, вычитая 1 больше, чем аккумулятор из входа.

({}[({}())()])

Мы можем поместить это в фрагмент выше

([(({}[({}())()])[()])]<>){<>({}())}{}<>{}

Это помещается в цикл, поэтому он выполняется до тех пор, пока мы не переключим стеки. Как только цикл заканчивается, мы извлекаем аккумулятор, переключая стеки и удаляя ненужные.

Мастер пшеницы
источник
2

Pyth , 7 байт

lh{I#./

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

Фильтруйте целочисленные разделы, которые не Iзависят от дедупликации, сохраняйте целочисленные разделы и получайте hихl значение.

Доказательство действительности

Не очень строгий и не сформулированный.

Пусть A = a 1 + a 2 + ... + а п и B = B 1 + B 2 + ... + Ь т две различные разделы одноготого же целого числа N . Предположим, что A - самое длинное уникальное разбиение. После того, как мы дедуплицируем B , то есть заменяем несколько вхождений одного и того же целого числа только одним из них, мы знаем, что сумма B меньше, чем N, . Но мы также знаем, что результат функции увеличивается (не строго), поэтому мы можем сделать вывод, что самый длинный уникальный раздел A всегда имеет по крайней мере такое же количество элементов, что и количество уникальных элементов в других разделах. ,

Мистер Xcoder
источник
2

Треугольность , 49 байтов

....)....
...2)2...
..)1/)8..
.)1/)IE/.
@^)1_+/i.

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

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

Треугольность требует, чтобы код имел треугольное распределение точек. То есть длина каждой строки должна быть равна числу строк, умноженному на 2 и уменьшенному, и каждая строка должна иметь (с каждой стороны) количество точек, равное ее позиции в программе (нижняя строка - строка 0, тот, что выше, это строка 1 и т. д.). Есть только пара команд, и любой символ, кроме тех, которые перечислены на странице 'Wiki / Commands', обрабатывается как недопустимый (посторонние точки никак не влияют на программу, пока общая форма программы остается прямоугольной).

Обратите внимание, что для команд с двумя аргументами я использовал a и b в объяснении. Имея это в виду, давайте посмотрим, что делает настоящая программа, после удаления всех посторонних символов, которые восполняют отступы:

)2)2)1/)8)1/)IE/@^)1_+/i | Input from STDIN and output to STDOUT.

)                        | Push a 0 onto the stack. Must precede integer literals.
 2                       | Push ToS * 10 + 2 (the literal 2, basically).
  )2                     | Again, push a 2 onto the stack. This can be replaced by D
                         | (duplicate), but then the padding would discard the saving.
    )1                   | Literal 1.
      /                  | Division. Push b / a (1 / 2).
       )8)1              | The literal 8 and the literal 1 (lots of these!).
           /             | Division. Push b / a (1 / 8).
            )IE          | Get the 0th input from STDIN and evaluate it.
               /         | Divide it by 1 / 8 (multiply by 8, but there isn't any
                         | operand for multiplication, and I'm not willing to add one).
                @        | Add 1 to the result.
                 ^       | Exponentiation. Here, it serves as a square too.
                  )1_+   | Decrement (add literal -1).
                      /  | Divide (by 2).
                       i | Cast to an integer.

Альтернативное решение и короче, если заполнение не требуется:

....)....
...2)1...
../DD)I..
.E/)4)1/.
+^s_+i...

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

Мистер Xcoder
источник
2

PowerShell 3.0, 45 байт

[math]::Sqrt(2*$args[0]+.25)-.5-replace'\..*'

Математический колл больно, а округление банкира PS - это настоящий дьявол (следовательно, ему нужно регулярное выражение для усечения, чтобы сохранить байт), но это выглядит довольно хорошо.

Veskah
источник
2

Java (JDK) , 28 байт

n->~-(int)Math.sqrt(8*n+1)/2

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

Потому что пример действительно не был удачным: p

кредиты

Оливье Грегуар
источник
1
28 байт " Потому что ваш код был действительно не очень удачным "; p
Кевин Круйссен
@KevinCruijssen Ну, теперь это так! : o
Оливье Грегуар
1

Желе , 7 байт

ŒPfŒṗṪL

Работает примерно за O (2 н ) времени.

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

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

ŒPfŒṗṪL  Main link. Argument: n

ŒP       Powerset; yield all subarrays of [1, ..., n], sorted by length.
   Œṗ    Yield all integer partitions of n.
  f      Filter; keep subarrays that are partitions.
     Ṫ   Tail; extract the last result.
      L  Compute its length.
Деннис
источник
1

JavaScript (ES7), 22 19 байт

n=>(8*n+1)**.5-1>>1

-3 байта благодаря ETHproductions.


Попытайся

o.innerText=(f=
n=>(8*n+1)**.5-1>>1
)(i.value=1000000000);oninput=_=>o.innerText=f(+i.value)
<input id=i type=number><pre id=o>


объяснение

Умножьте входное значение на 8 и прибавьте 1, увеличьте его до степени .5, получив квадратный корень, вычтите 1 и сдвиньте результат сдвига вправо на 1.

мохнатый
источник
Можете ли вы включить объяснение? Я давно не делал Javascript
FantaC
Как n=>(8*n+1)**.5-1>>1сохранить 3 байта? (не проверял)
ETHproductions
Я переиграл это в JS: codegolf.stackexchange.com/a/152558/21830
Unihedron
@ETHproductions - похоже, это работает, спасибо.
Лохматый
@tfbninja, я бы подумал, что это довольно очевидно, но объяснение добавлено.
Лохматый
1

Python 2/3, 32 байта

Python реализация формулы закрытой формы

lambda n:int((sqrt(1+8*n)-1)//2)

Целочисленное деление //2округляет до нуля, поэтому не floor( )требуется

Карл дер Кафер
источник
1
Добро пожаловать в PPCG! Это должно from math import sqrtработать? Если так, это должно быть включено в bytecount. (В этом случае lambda n:int((math.sqrt(1+8*n)-1)//2) import math немного короче. )
Steadybox
29 байт
FlipTack
Да, для работы требуется импорт, поэтому его следует включить в число байтов.
mbomb007
1

Haskell , 28 байт

В некотором роде скучно, но оно намного короче, чем другое решение на Haskell, и имеет действительно приятное, бессмысленное выражение. К сожалению, я не мог бы сделать это короче без мешающей системы типов:

g x=floor$sqrt(2*x+0.25)-0.5

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

Pointfree, 33 байта

ceiling.(-0.5+).sqrt.(0.25+).(2*)

В качестве альтернативы, 33 байта

Та же длина, что и у точечной версии, но гораздо интереснее.

g n=sum[1|x<-scanl1(+)[1..n],n>x]
ბიმო
источник
Мне удалось связать формулу , исправив некоторые глупые ошибки!
полностью человек
@totallyhuman: Хорошо, теперь и ты намного лучше :)
მოიმო
1

Млечный Путь , 12 байт

'8*1+g1-2/v!

объяснение

code         explanation       value

'            push input        n          
 8*          push 8, multiply  8n
   1+        add 1             8n+1
     g       square root       sqrt(8n+1)
      1-     subtract 1        sqrt(8n+1)-1
        2/   divide by 2       (sqrt(8n+1)-1)/2
          v  floor             floor((sqrt(8n+1)-1)/2)
           ! output
овс
источник
1

Пыть , 7 5 байт

Đř△>Ʃ

Объяснение:

                      Implicit input
Đř△                   Gets a list of the first N triangle numbers
   >                  Is N greater than each element in the list? (returns an array of True/False)
    Ʃ                 Sums the list (autoconverts booleans to ints)



Быстрее, но дольше

Пыть , 11 9 байт

Đ2*√⌈ř△>Ʃ

Объяснение:

Đ2*√⌈ř△           Gets a list of triangle numbers up to the ceiling(sqrt(2*N))-th
       >          Is N greater than each element of the list? (returns an array of True/False)
        Ʃ         Sums the array



Альтернативный способ - порт Шегги

Пыть , 8 7 байт

8*⁺√⁻2÷
mudkip201
источник
1

Пробел , 111 байт

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_integer_from_STDIN][T T   T   _Retrieve_input][S S S T    S S S N
_Push_8][T  S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][S S T   T   N
_Push_n=-1][N
S S N
_Create_Label_SQRT_LOOP][S S S T    N
_Push_1][T  S S S _Add][S N
S _Duplicate_n][S N
S _Duplicate_n][T   S S N
Multiply][S T   S S T   S N
_Copy_0-based_2nd_(the_input)][S S S T  N
_Push_1][T  S S S _Add][T   S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_SQRT_LOOP][S S S T   S N
_Push_2][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer_divide][T    N
S T _Print_integer]

Буквы S(пробел), T(табуляция) и N(новая строка) добавляются только как подсветка.
[..._some_action]добавлено только в качестве объяснения.

Попробуйте онлайн (только с необработанными пробелами, вкладками и новыми строками).

Объяснение в псевдокоде:

Использует формулу:

еNзнак равно8N+1-12

ПРИМЕЧАНИЕ. В пробелах нет встроенного квадратного корня, поэтому мы должны сделать это вручную.

Integer i = read STDIN as integer
i = i * 8 + 1
Integer n = -1
Start SQRT_LOOP:
  n = n + 1
  If(n*n < i+1):
    Go to next iteration of SQRT_LOOP
n = (n - 2) integer-divided by 2
Print n as integer to STDOUT
Кевин Круйссен
источник
0

Витси , 16 байтов

2*14/+12/^12/-_N

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

Могу также добавить свой собственный вклад в микс. Это короче, чем решение итераций разбиения в Vitsy.

Аддисон Крамп
источник
0

Оазис , 14 байт

n8*1+1tm1%_b+0

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

Как?

n8*1+           8n + 1
     1tm        sqrt
        1%_     integer?
           b+   add f(n-1)

             0  f(0) is 0

Это рекурсивное решение, которое увеличивает результат, когда встречает треугольный индекс, начиная с 0 для ввода 0.

Уриэль
источник
0

Рубин , 27 байт

Три по цене одного. Я разочарован тем, что не могу идти короче.

->n{a=0;n-=a+=1while n>a;a}
->n{((8*n+1)**0.5-1).div 2}
->n{((n-~n)**0.5-0.5).to_i}

Попробуйте онлайн! (чтобы выбрать функцию, добавьте перед ней f =)

Unihedron
источник