Ближайшие номера разделов

12

Число разделов целого числа - это количество способов, которыми целое число может быть представлено как сумма положительных целых чисел.

Например:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Существует 7 способов представления числа 5, поэтому 7 - это номер раздела, соответствующий числу 5.

Номера разделов: OEIS: # A000041

Направления

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

  • На входе должно быть 1 положительное целое число.
  • Если входное значение не является номером раздела, выходное значение должно быть двумя различными положительными целыми числами, которые генерируют два ближайших номера раздела к входному номеру. (Если два номера разделов являются равными кандидатами на один из выходных номеров, не имеет значения, какой из них вы выберете.)
  • Если входной сигнал представляет номер раздела, выход должен быть положительным целым числом 1 , который генерирует номер входа.
  • Ввод и вывод могут быть в любом разумном формате.
  • Вы можете предположить, что входное значение не будет больше 100 миллионов (например, выходное значение никогда не будет больше 95).
  • Встроенные функции для расчета номеров разделов не допускаются, как и другие стандартные лазейки .
  • Это код-гольф , поэтому выигрывает наименьшее количество байтов.

Номера разделов: OEIS: # A000041

Примеры

Input: 66
Output: 11, 12

(Номера разделов, которые соответствуют номерам 11 и 12, равны 56 и 77, которые являются двумя ближайшими номерами разделов к 66.)

Input: 42
Output: 10

(Число 42 уже является номером раздела, поэтому просто выведите номер, соответствующий номеру раздела.)

Input: 136
Output: 13, 14

(Два ближайших номера раздела 136 на самом деле оба МЕНЬШЕ, чем 136 (например, 101 и 135), поэтому на выходе получается 13 и 14, а не 14 и 15.)

Input: 1
Output: 0   or   1

(И 0, и 1 являются действительными выходами в этом особом случае.)

Input: 2484
Output: 26, 25   or   26, 27

(Оба этих выходы действительны, поскольку 2484 равен д я позиция с 1958 и 3010.)

Input: 4
Output: 3, 4

(Ага)

code-golf number-theory integer-partitions kukac67
источник
Вы не определили, что такое номер раздела
гордый haskeller
@proudhaskeller Номера разделов - это номера, связанные в последовательности OEIS. Объяснение того, для чего номер раздела 5, находится вверху. (Я добавлю пояснения, если вы считаете, что это недостаточно ясно.)
kukac67
1
Это очень близко к тому, чтобы быть дураком из этого более раннего вопроса о разделе .
Питер Тейлор

Ответы:

2

Pyth , 53

L?!b<b1sm&d*^_1tdy-b/*dt*3d2r_bhbJo^-QyN2U99<J-2qQyhJ

Объяснение и больше игры в гольф, чтобы следовать.

isaacg
источник
4

Python 2, 179 байт

Z=range(1,99)
R=Z+[1]
for i in Z:R[i]=sum(-(-1)**k*(3*k*k-k<=i*2and R[i-k*(3*k-1)/2])for k in range(-i,i+1)if k)
f=lambda n:zip(*sorted((abs(n-R[i]),i)for i in Z))[1][:2-(n in R)]

Использует рекурсивную формулу из пятиугольной теоремы Эйлера .

Позвони с f(2484). Выход - это кортеж с одним или двумя числами.

Sp3000
источник
2

Mathematica, 124 123 байта

f@n_:=(p=SeriesCoefficient[1/Product[1-x^k,{k,#}],{x,0,#}]&;s=SortBy[Range@95,Abs[n-p@#]&];If[p@s[[1]]==n,s[[1]],s~Take~2])

Формула для номеров разделов взята со страницы OEIS . (Может или нет обманывать ... Я не мог решить.)

Использование:

In: f[136]

Out: {14, 13}

Я не отвечаю на победу. И я уверен, что это может быть дальше.

kukac67
источник