13
\$\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
  • 1
    \$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Jelly, 17 bytes

eⱮRŒṗẈrƝƲTµ;‘ṁ3ḊQ

Try it online!

Outputs in reverse order.

I think this just about follows the rule "Built-in functions to calculate partition numbers are not allowed", as this uses the Jelly builtin to calculate the list of integer partitions, not the number of partitions. For example, 4Œṗ => [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]].

How it works

eⱮRŒṗẈrƝƲTµ;‘ṁ3ḊQ - Main link. Takes an input n on the left
        Ʋ         - Group the previous 4 links together:
  R               -   Take the range 1...n
   Œṗ             -   Calculate the partitions of each k in the range
     Ẉ            -   Take the length of each.
                  -   This gives the kth partition number
      rƝ          -   Insert ranges for each overlapping pair of partition numbers
 Ɱ                - For each of the list of ranges...
e                 -   Yield 1 if n is in the range between the kth and (k+1)th partition number and 0 otherwise
         T        - Remove 0s and replace 1s with their index
                  - For partition numbers, this yields two values. If m is the desired output, this yields [m-1, m]
                  - For non-partition numbers, this returns [m], when the required output is [m, m+1]
          µ       - Set the return value to either U = [m-1, m] or U = [m]
            ‘     - Yield [m, m+1] or [m+1]
           ;      - Concatenate to U, giving either [m-1, m, m, m+1] or [m, m+1]
             ṁ3   - Mold to length 3, giving either [m-1, m, m] or [m, m+1, m]
               Ḋ  - Remove the first value, returns [m, m] or [m+1, m]
                Q - Remove duplicates and output either [m] or [m+1, m]
| improve this answer | |
\$\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.