14
\$\begingroup\$

For a given number n, output an strictly decreasing array whose sum is n and its lexicographical order is the smallest for any possible outputs

Smallest lexicographical order means that for or sum n=9 the following strictly decreasing arrays are possible: [[9],[8,1],[7,2],[6,3],[5,4],[6,2,1],[5,3,1],[4,3,2]]. Putting these in lexicographical order: [[4,3,2],[5,3,1],[5,4],[6,2,1],[6,3],[7,2],[8,1],[9]], the first [4,3,2] will be the final output

Testcases

4 -> [3,1]
9 -> [4,3,2]
10 -> [4,3,2,1]
20 -> [6,5,4,3,2]

You may assume that n>0 and that you are allowed to output any human readable form of characters to represent the array of numbers

Note that a strictly decreasing array has no duplicates so the array cannot be [1,1,1...]

This is , so shortest code wins!

Improve this question
\$\endgroup\$
0

14 Answers 14

Reset to default
14
\$\begingroup\$

JavaScript (Node.js), 38 bytes

f=n=>n?[p=.5+(n+n)**.5|0,...f(n-p)]:[]

Try it online!

That is, find out the smallest \$x\$ where

$$ \sum_{i=1}^{x}i= \frac{(x+1)\cdot x}{2}\ge n $$

which is

$$ x=\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil $$

As att and Bubbler suggested in the comments. This formula could be simplified into

$$ x=\left\lfloor\sqrt{2n}+\frac{1}{2}\right\rfloor $$

Improve this answer
\$\endgroup\$
4
  • 3
    \$\begingroup\$ You don't need the \$+\frac14\$. \$\endgroup\$
    – att
    Commented Mar 7, 2022 at 3:37
  • \$\begingroup\$ @att Seems to be correct by testing up to 1e8. But I don't quite understand why. Will there be any proof? \$\endgroup\$
    – tsh
    Commented Mar 7, 2022 at 5:41
  • 3
    \$\begingroup\$ Rough proof: The change is equivalent to changing 8n+1 to 8n in the second line. There the value of x does not change if the "ceil-to-odd-square" (the smallest odd square number >= input) of 8n+1 is the same as that of 8n. If the value were to change, 8n should be the upper bound of a lower range and therefore an odd square, which is a contradiction. \$\endgroup\$
    – Bubbler
    Commented Mar 7, 2022 at 6:32
  • \$\begingroup\$ Also, this transformation now makes the expression inside ceil always a non-integer, so you can convert it to floor of +1, which gives 38 bytes. \$\endgroup\$
    – Bubbler
    Commented Mar 7, 2022 at 6:44
4
\$\begingroup\$

Vyxal, 7 6 bytes

Ṅ~Þush

Try it Online!

-1 thanks to EmanresuA reminding me that ~ exists.

Explained

Ṅ~Þush
Ṅ      # From all integer partitions of the input,
 ~     # Keep only partitions where:
  Þu   #   The uniqufied version equals the partition (this makes sure that only partitions without duplicates are kept)
    sh # Sort the list and take the first item
Improve this answer
\$\endgroup\$
1
4
\$\begingroup\$

Wolfram Language (Mathematica), 39 37 bytes

f@n_:=#<>f[n-#]&@Round@√(2n)
f@0=""

Try it online!

Returns a StringJoin of integers.

Wolfram Language (Mathematica), 37 bytes

Last@Pick[s=Subsets@Range@#,Tr/@s,#]&

Try it online!

Returns the partition in increasing order. For decreasing order, +4 bytes: Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ (1) Since the OP asks for a "strictly decreasing array", I think your output for Last@Pick[s=Subsets@Range@#,Tr/@s,#]& needs to be reversed. (2) I didn't know it was permitted to provide an answer in the functional form you gave with f@n_:=#<>f[n-#]&@Round@√(2n) f@0="", so that's good to know. But I don't know whether a StringJoin of integers qualifies as an array. \$\endgroup\$
    – theorist
    Commented Mar 8, 2022 at 6:53
  • \$\begingroup\$ @theorist I agree on (1), but I felt it was interesting enough to leave be. As for (2), I'm fairly liberal with list output formats, since pretty much any expression with arguments can be interpreted as one; StringJoin is nice to use since it's Flat and <> is short. I do consider List and Sequence to be more "pure" though; we can convert it into Sequence output for 41 bytes. \$\endgroup\$
    – att
    Commented Mar 8, 2022 at 8:28
3
\$\begingroup\$

Pyth, 19 16 13 11 10 bytes

hf{ITS_M./

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

C# (Visual C# Interactive Compiler), 107 bytes

x=>{var y=new List<int>();while(x!=0){y.Add((int)Math.Ceiling((Math.Sqrt(x*8+1)-1)/2));x-=y[^1];}return y;}

Try it online!

I think i can save a few bytes somewhere here, but i can't quite figure it out. Haskell tricks with unrolling multiple arguments comes to mind but it's been too long since i golfed properly to remember it (Lost access to old account when school email expired feelsbad). feel free to improve this and take the points. Uses the same approach as the Javascript answer, but without the JS list comprehension tricks. In other words, find the lowest value such that the sum from 1 to n is greater than x, push that to the list, subtract n from x and repeat until x is 0.

From my early tests, using Floor and the third formula is the same number of characters in C#, though i couldn't really get it working.

This can save a bunch of characters by taking an empty list as a parameter and editing/filling it in place (removes the need for the "new" and the return, effectively making the outer function a one-liner. Further, it could be made recursive, which removes the while loop, though idk if that actually saves anything), but i'd guess that's blocked by loophole rules.

making the list a list of double will save 2 bytes but the results are then doubles, and this raises the possibility of floating point nonsense and potentially printing out 3.0000000004 or something similar.

Edit: Uses the new Index object and it's ^ operator, introduced in C# 8.0. Not normally a fan b/c it makes the code more obtuse, but it's perfect for code golf. ^1 is shorthand for the last element in the list.

Improve this answer
\$\endgroup\$
1
3
\$\begingroup\$

05AB1E, 8 bytes

Læí.ΔOQ

Try it online or verify all test cases.

Explanation:

L        # Push a sum in the range [1, (implicit) input]
 æ       # Pop and get the powerset of this
         # (which is already in the correct order)
  í      # Reverse each inner list to make the inner lists in decreasing order
   .Δ    # Keep the first inner list that's truthy for:
     O   #  Where the sum
      Q  #  Equals the (implicit) input
         # (after which this found result is output implicitly)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Husk, 8 bytes

↔ḟo=¹ΣṖḣ

Try it online!

Husk has no 'integer partitions' built-in, but since the array must be strictly decreasing (no duplicates) we can build it by selecting a subset of n..1 that sums to n.
If we do it the other way around (selecting from 1..n), then the first 'hit' is already the right set, and we just need to reverse the order of its elements to make it decreasing.

       ḣ  # start with range 1..input:
      Ṗ   # get all subsequences;
↔ḟo       # now get the first element that satisfies:
     Σ    #   its sum
   =¹     #   equals the input;
↔         # and finally reverse it.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Haskell, 45 bytes

f 0=[]
f n=[a:f(n-a)|a<-[1..n],[a]>f(n-a)]!!0

Try it online!

f(n) searches, starting from a = 1 , a list to append to a :

  • lexicographically less than a,
    that sums to n (with a).

Such list is f( n-a ).

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

R, 46 bytes

f=function(n)if(n)c(p<-round((2*n)^.5),f(n-p))

Try it online!

Reproducing tsh resolution in R.

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Nice! You should include the f= as part of the byte count, though, since the name of the function is needed for it to run correctly. Otherwise you can use Recall (like this), but it isn't very golfy... \$\endgroup\$
    – Dominic van Essen
    Commented Mar 9, 2022 at 12:22
3
\$\begingroup\$

Factor + math.combinatorics math.unicode, 56 bytes

[ dup 1 [a,b] all-subsets [ Σ = ] with filter infimum ]

Try it online!

  • 1 [a,b] all-subsets Powerset of n..1
  • dup ... [ Σ = ] with filter Select the subsets that sum to the input
  • infimum Get the smallest one
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 30 bytes

.+
$*
(?=(\G1|1\1)*1)1\1?
$.&¶

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

(?=(\G1|1\1)*1)1\1?

Repeatedly match the smallest number whose triangular number exceeds the remainder, calculated as one more than the largest number whose triangular number is strictly less than the input.

$.&¶

Convert to decimal and list each number on its own line.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3.8 (pre-release), 45 bytes

Inspired by the answer of user tsh. -9 bytes thanks to user att.

lambda n:n*[p:=round((2*n)**.5)]and[p]+f(n-p)

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Jelly, 7 bytes

ŒṗUQƑƇṂ

Try it online!

The only real difference from lyxal's Vyxal solution is that Jelly's integer partitions builtin generates them in nondecreasing order, requiring them to be reversed before finding the minimum.

ŒṗU        Nonincreasing integer partitions.
     Ƈ     Filter to those which
    Ƒ      are unchanged by
   Q       uniquification.
      Ṃ    Take the minimum.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 21 bytes

ＮθＷＬΦθ‹Σ…·⁰κθ«≧⁻ιθ⟦Ｉι

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

ＷＬΦθ‹Σ…·⁰κθ«

Count how many triangular numbers starting from 0 are less than n and repeat until this becomes zero.

≧⁻ιθ

Subtract that number from n.

⟦Ｉι

Output that number on its own line.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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