12
\$\begingroup\$

The number of partitions of an integer is the number of ways that integer can be represented as a sum of positive integers.

For example:

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

There are 7 ways to represent the number 5, therefore 7 is the partition number corresponding to the number 5.

Partition numbers: OEIS: #A000041

Directions

Write a program that takes a positive integer as input, and outputs the two numbers that generate the two closest partition numbers to the input number.

  • Input must be 1 positive integer.
  • If the input is not a partition number, the output must be the 2 different positive integers that generate the two closest partition numbers to the input number. (If two partition numbers are equal candidates for one of the output numbers, it doesn't matter which one you choose.)
  • If the input is a partition number, the output must be 1 positive integer that generates the input number.
  • Input and output may be in any reasonable format.
  • You may assume that the input will not be larger than 100 million (eg. output will never be larger than 95).
  • Built-in functions to calculate partition numbers are not allowed, along with other Standard loopholes.
  • This is , so least number of bytes wins.

Partition numbers: OEIS: #A000041

Examples

Input: 66
Output: 11, 12

(The partition numbers that correspond to the numbers 11 and 12 are 56 and 77, which are the two closest partition numbers to 66.)

Input: 42
Output: 10

(The number 42 is already a partition number, so just output the number that corresponds to the partition number.)

Input: 136
Output: 13, 14

(The two closest partition numbers to 136 are actually both LESS than 136 (eg. 101 and 135), therefore the output is 13 and 14 as opposed to 14 and 15.)

Input: 1
Output: 0   or   1

(Both 0 and 1 are valid outputs in this special case.)

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

(Both of these outputs are valid, because 2484 is equal distance from 1958 and 3010.)

Input: 4
Output: 3, 4

(Yup)

\$\endgroup\$
  • \$\begingroup\$ You didn't define what is a partition number \$\endgroup\$ – proud haskeller Dec 26 '14 at 18:44
  • \$\begingroup\$ @proudhaskeller Partition numbers are the numbers that are in the OEIS sequence linked. Explanation for what the partition number for 5 is is at the top. (I'll add clarification if you think it's not clear enough.) \$\endgroup\$ – kukac67 Dec 26 '14 at 18:51
  • 1
    \$\begingroup\$ This is very close to being a dupe of this earlier partition question. \$\endgroup\$ – Peter Taylor Dec 26 '14 at 20:47
2
\$\begingroup\$

Pyth, 53

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

Explanation and more golfing to follow.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 179 bytes

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

Uses the recursive formula from Euler's pentagonal theorem.

Call with f(2484). Output is a tuple with one or two numbers.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 124 123 bytes

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

Formula for partition numbers taken from the OEIS page. (May or may not be cheating... I couldn't decide.)

Usage:

In: f[136]

Out: {14, 13}

I'm not answering to win. And I'm sure this could be golfed further.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.