Trouver le plus grand nombre d'entiers distincts totalisant n

18

La tâche

Étant donné un entier positif en entrée n(de 1 à la limite de votre langue, inclusivement), retournez ou sortez le nombre maximum d'entiers positifs distincts qui totalisent n.

Cas de test

Soit fdéfinir une fonction valide en fonction de la tâche:

La séquence pour f, à partir de 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, ...

En tant que cas de test plus grand:

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

Code de test

Pour tous les cas de test non explicitement fournis, la sortie de votre code doit correspondre au résultat de ce qui suit:

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));
    }
}

Essayez-le en ligne!

Addison Crump
la source
Peut-il être indexé 0?
2018 totalement humain
1
@totallyhuman "ce" étant les réponses? Parce qu'il ne s'agit pas d'une liste ...
Addison Crump
3
@totallyhuman Non. Il s'agit des partitions distinctes de nombres spécifiques.
Addison Crump
5
Il s'agit d' OEIS A003056 .
Jeppe Stig Nielsen
4
Je me sens insignifiant à chaque fois que je tombe sur la pile de codegolf. Les réponses et les commentaires sont bien plus que de l'humilité. Les questions sont généralement intéressantes aussi, mais avec son commentaire @JeppeStigNielsen jette simplement les plans achevés alors que nous envisageons toujours la surface au sol.
KalleMP

Réponses:

9

05AB1E , 4 octets

ÅTg<

Essayez-le en ligne!

Outil parfait pour le travail.

ÅTdonne la liste des Å ll T numéros riangular jusqu'au N (y compris , malheureusement , 0 aussi, sinon il serait 3 octets), g<obtient le len g e et décrémente.

M. Xcoder
la source
8

Gelée , 6 5 octets

R+\»ċ

Essayez-le en ligne!

Assez efficace. Cette séquence s'incrémente aux nombres triangulaires, donc cela compte juste combien de nombres triangulaires sont plus petits que n .

Explication:

        # 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
la source
Dans l'explication, vous voulez sûrement dire "combien de nombres sont inférieurs ou égaux à n "
Luis Mendo
@LuisMendo Voir la nouvelle explication.
DJMcMayhem
6

Haskell , 26 octets

-2 octets grâce à H.PWiz.

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

Essayez-le en ligne!

Cela renvoie le nième élément des nombres entiers où chaque i est répliqué i + 1 fois.

totalement humain
la source
3
Je ne peux pas m'empêcher de demander ce qu'est le "succ"
Addison Crump
Ouais, je sais lol. succreprésente successor.
2018
5

Brain-Flak , 36 octets

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

Essayez-le en ligne!

Il utilise la même structure que l'algorithme de division standard, sauf que le "diviseur" est incrémenté à chaque lecture.

Nitrodon
la source
3

Brain-Flak , 82 octets

Ajout d'un espace blanc pour la "lisibilité"

(())

{
    {}

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

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

}{}{}{}

([]<>)

Essayez-le en ligne!

DJMcMayhem
la source
Compétition comme toujours
Post Rock Garf Hunter
1
Qui aurait pensé que combiner deux langages illisibles, Whitespace et Brain-Flak, pourrait être considéré comme "lisible"!
caird coinheringaahing
3

R , 28 octets

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

Essayez-le en ligne!

Crée le vecteur des temps 1répétés 2, 2des 3temps répétés , ..., ndes n+1temps répétés et prend l' nthélément. Cela entraînera une erreur de mémoire soit parce qu'elle 1:nest trop grande, soit parce que la liste répétée avec des n*(n+1)/2 - 1éléments est trop grande.

R , 29 octets

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

Essayez-le en ligne!

Calcule la valeur directement, en utilisant la formule trouvée dans la réponse d'alephalpha . Cela devrait fonctionner sans problème, à part la précision numérique possible.

R , 30 octets

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

Essayez-le en ligne!

Compte les nombres triangulaires inférieurs ou égaux à n. Ce sera peut-être une erreur de mémoire si elle 1:nest suffisamment grande - par exemple, 1e9elle lance Error: cannot allocate vector of size 3.7 Gb.

Giuseppe
la source
2

TI-Basic, 12 octets

int(√(2Ans+1/4)-.5
Timtech
la source
2

JavaScript (Node.js) , 18 octets

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

Essayez-le en ligne!

Unihedron
la source
Est-ce toujours correct? Je ne suis pas certain floor((sqrt(8x+4)-1)/2)(votre formule) et floor((sqrt(8x+1)-1)/2)(formule correcte) donnent le même résultat pour chaque x.
ETHproductions
@ETHproductions Je pourrais bluffer et dire "oui", mais je pense que la réponse la plus honnête est que vous devriez essayer de développer votre propre hypothèse et de déterminer si / pourquoi elle reflète la même formule. Je n'ai pas trouvé cette approche par moi-même (je l'ai apprise sur un autre site) mais j'ai joué un peu avec. C'est une approche très intéressante et je ne veux pas disséquer la grenouille si tôt.
Unihedron
Hmm. Je ne sais pas comment le prouver directement, mais j'ai écrit un brute-forcer qui ne trouve aucun échec inférieur à 100 millions.
ETHproductions
2

Japt , 8 octets

Solution de formule fermée.

*8Ä ¬É z

Essayez-le


Explication

Multipliez par 8, ajoutez 1 ( Ä), obtenez la racine carrée ( ¬), soustrayez 1 ( É) et plancher divisez le résultat par 2 ( z).


Alternative, 8 octets

Port de la solution Jelly de DJMcMayhem .

õ å+ è§U

Essayez-le

Générez un tableau d'entiers ( õ) de 1 à l'entrée, réduisez cumulativement ( å) par addition ( +) et comptez ( è) les éléments inférieurs ou égaux à ( §) l'entrée ( U).

Hirsute
la source
2

Brain-Flak , 70 56 48 octets

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

Essayez-le en ligne!

Explication

La partie principale de ceci est l'extrait suivant que j'ai écrit:

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

Cela ne fera rien si le TOS est positif et changera de pile dans le cas contraire. C'est super pile impur mais ça marche. Maintenant, la partie principale du programme soustrait des nombres de plus en plus importants de l'entrée jusqu'à ce que l'entrée soit non positive. Nous démarrons l'accumulateur à 1 à chaque fois en soustrayant 1 de plus que l'accumulateur de l'entrée.

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

Nous pouvons mettre cela à l'intérieur de l'extrait ci-dessus

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

Cela est mis en boucle pour qu'il s'exécute jusqu'à ce que nous changions de pile. Une fois la boucle terminée, nous récupérons l'accumulateur en changeant de pile et en supprimant les fichiers indésirables.

Post Rock Garf Hunter
la source
2

Pyth , 7 octets

lh{I#./

Essayez-le en ligne!

Filtrez-gardez les partitions entières qui sont Invariantes par rapport à la déduplication, saisissez l' head et obtenez sonl ength.

Preuve de validité

Pas très rigoureux ni bien formulé.

Soit A = a 1 + a 2 + ... + a n et B = b 1 + b 2 + ... + b m soit deux partitions distinctes d'un même nombre entier N . Nous supposerons que A est la partition unique la plus longue . Après nous dédupliquer B , qui est, remplacer plusieurs occurrences du même entier avec un seul d'entre eux, nous savons que la somme de B est inférieure à N . Mais nous savons également que le résultat de la fonction augmente (non strictement), nous pouvons donc déduire que la partition unique A la plus longue a toujours au moins la même quantité d'éléments que le nombre d'éléments uniques dans d'autres partitions.

M. Xcoder
la source
2

Triangularité , 49 octets

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

Essayez-le en ligne!

Comment ça fonctionne

La triangularité nécessite que le code ait une distribution triangulaire des points. Autrement dit, la longueur de chaque ligne doit être égale au nombre de lignes multiplié par 2 et décrémenté, et chaque ligne doit avoir (de chaque côté) un nombre de points égal à sa position dans le programme (la ligne du bas est la ligne 0, celui au-dessus est la ligne 1 et ainsi de suite). Il n'y a que quelques commandes, et tout caractère autre que ceux répertoriés sur la page 'Wiki / Commandes' est traité comme un no-op (les points étrangers n'affectent en rien le programme, tant que la forme globale du programme reste rectangulaire).

Notez que pour les commandes à deux arguments, j'ai utilisé un et b tout au long de l'explication. Gardant cela à l'esprit, voyons ce que fait le programme réel, après avoir supprimé tous les caractères étrangers qui composent le remplissage:

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

Une solution alternative, et plus courte si le rembourrage n'est pas nécessaire:

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

Essayez-le en ligne!

M. Xcoder
la source
2

PowerShell 3.0, 45 octets

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

L'appel mathématique fait mal et l'arrondi du banquier de PS est le diable réel (d'où la nécessité de regex pour tronquer pour enregistrer un octet), mais cela semble assez bien.

Veskah
la source
2

Java (JDK) , 28 octets

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

Essayez-le en ligne!

Parce que l'exemple n'était vraiment pas bien joué: p

Crédits

Olivier Grégoire
la source
1
28 octets " Parce que votre code n'était vraiment pas bien joué "; p
Kevin Cruijssen
@KevinCruijssen Eh bien, c'est maintenant! : o
Olivier Grégoire
1

Gelée , 7 octets

ŒPfŒṗṪL

Fonctionne approximativement en temps O (2 n ) .

Essayez-le en ligne!

Comment ça fonctionne

Œ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.
Dennis
la source
1

JavaScript (ES7), 22 19 octets

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

-3 octets grâce à ETHproductions.


Essayez-le

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>


Explication

Multipliez l'entrée par 8 et ajoutez 1, augmentez cela à la puissance de 0,5, en nous donnant la racine carrée, soustrayez 1 et décalez le résultat de 1 à droite.

Hirsute
la source
Pouvez-vous inclure une explication? Je n'ai pas fait Javascript depuis un moment
FantaC
Comment n=>(8*n+1)**.5-1>>1économiser 3 octets? (non testé)
ETHproductions
J'ai surclassé ceci dans JS: codegolf.stackexchange.com/a/152558/21830
Unihedron
@ETHproductions - on dirait que ça marche, merci.
Shaggy
@tfbninja, j'aurais pensé assez explicite mais une explication a été ajoutée.
Shaggy
1

Python 2/3, 32 octets

Implémentation Python de la formule sous forme fermée

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

La division entière est //2arrondie vers zéro, donc pas floor( )nécessaire

Karl der Kaefer
la source
1
Bienvenue chez PPCG! Cela doit-il from math import sqrtfonctionner? Si tel est le cas, il doit être inclus dans le bytecount. (Dans ce cas, lambda n:int((math.sqrt(1+8*n)-1)//2) import math c'est un peu plus court. )
Steadybox
29 octets
FlipTack
Oui, il a besoin de l'importation pour fonctionner, donc cela devrait être inclus dans le nombre d'octets.
mbomb007
1

Haskell , 28 octets

Un peu ennuyeux, mais il est assez court que l 'autre solution Haskell et a une très belle expression sans point. Malheureusement, je ne pouvais pas le raccourcir sans que le système de type ne gêne:

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

Essayez-le en ligne!

Sans point, 33 octets

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

Alternativement, 33 octets

Même longueur que la version sans point, mais beaucoup plus intéressante.

g n=sum[1|x<-scanl1(+)[1..n],n>x]
ბიმო
la source
J'ai réussi à lier la formule en corrigeant quelques erreurs stupides!
2018 totalement humain à 15h08
@totallyhuman: Nice, maintenant à vous est beaucoup plus agréable aussi :)
ბიმო
1

Voie lactée , 12 octets

'8*1+g1-2/v!

Explication

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
ovs
la source
1

Pyt , 7 5 octets

Đř△>Ʃ

Explication:

                      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)



Plus rapide, mais plus long

Pyt , 11 9 octets

Đ2*√⌈ř△>Ʃ

Explication:

Đ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



Voie alternative - port de la réponse Shaggy

Pyt , 8 7 octets

8*⁺√⁻2÷
mudkip201
la source
1

J , 11 octets

2&!inv<.@-*

Essayez-le en ligne!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
FrownyFrog
la source
J'aime ce truc avec *pour produire 1
Jonah
1

Espace blanc , 111 octets

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

Lettres S(espace), T(tabulation) etN (nouvelle ligne) ajoutées uniquement en surbrillance.
[..._some_action]ajouté à titre d'explication uniquement.

Essayez-le en ligne (avec des espaces bruts, des tabulations et des nouvelles lignes uniquement).

Explication en pseudo-code:

Utilise la formule:

Fn=8n+1-12

REMARQUE: les espaces blancs n'ont pas de racine carrée intégrée, nous devons donc le faire manuellement.

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
Kevin Cruijssen
la source
0

Vitsy , 16 octets

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

Essayez-le en ligne!

Autant ajouter ma propre contribution au mix. C'est plus court que la solution d'itérations de partition dans Vitsy.

Addison Crump
la source
0

Oasis , 14 octets

n8*1+1tm1%_b+0

Essayez-le en ligne!

Comment?

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

             0  f(0) is 0

Il s'agit d'une solution récursive qui incrémente le résultat lorsqu'il rencontre un index triangulaire, en commençant par 0 pour l'entrée 0.

Uriel
la source
0

Rubis , 27 octets

Trois pour le prix d'un. Je suis déçu de ne pas pouvoir aller plus court.

->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}

Essayez-le en ligne! (pour sélectionner la fonction, ajoutez f = devant)

Unihedron
la source