12
\$\begingroup\$

Left in sandbox for at least 3 days.

I want to verify if this inequality is true:

for \$n\geq4\$, if \$a_1,a_2,a_3,\dots,a_n\in R_+\cup\{0\}\$ and \$\sum_{i=1}^na_i=1\$, then \$a_1a_2+a_2a_3+a_3a_4+\dots+a_{n-1}a_n+a_na_1\leq\frac{1}{4}\$.

Challenge

Write a piece of program which takes an integer n as input. It does the following:

  1. Generate a random array a which consists of n non-negative reals. The sum of all elements should be 1.

By saying random, I mean, every array satisfiying the requirements in 2 should have a non-zero probability of occurrence. It don't need to be uniform. See this related post.

  1. Calculate a[0]a[1]+a[1]a[2]+a[2]a[3]+...+a[n-2]a[n-1]+a[n-1]a[0].

  2. Output the sum and the array a.

For I/O forms see this post.

Rules

(Sorry for the late edit...) All numbers should be rounded to at least \$10^{-4}\$.

Standard loopholes should be forbidden.

Example

The following code is an ungolfed Python code for this challenge, using library numpy. (For discussion about using libraries, see This Link.)

import numpy as np


def inequality(n):
    if n < 4:
       raise Exception
    a = np.random.rand(n)
    sum_a = 0
    for i in range(n):
        sum_a += a[i]
    for i in range(n):
        a[i] /= sum_a
    sum_prod = 0
    for i in range(n):
       sum_prod += a[i % n] * a[(i + 1) % n]
    print(a)
    return sum_prod, a

Tip

You could assume that input n is a positive integer greater than 3.


Your score is the bytes in your code. The one with the least score wins.

\$\endgroup\$
4
  • \$\begingroup\$ A test code can be found here. \$\endgroup\$ Feb 17 at 1:09
  • \$\begingroup\$ Would just like to note that, all of the answers are going to be generating and summing rationals, leaving almost all reals untested \$\endgroup\$
    – Cruncher
    Feb 17 at 15:06
  • \$\begingroup\$ @Cruncher Hard for computers to manipulate irrationals... will edit to noticeall numbers can be rounded to at least 4 digits? \$\endgroup\$ Feb 18 at 0:10
  • \$\begingroup\$ Yeah, that was exactly my point. Not saying it's an issue for the coding challenge, just being pedantic. Maybe the inequality trying to prove should be for Q+ and not R+ \$\endgroup\$
    – Cruncher
    Feb 18 at 17:41

14 Answers 14

4
\$\begingroup\$

APL(Dyalog Unicode), 21 bytes SBCS

(+/⊢×1∘⌽)⎕←(⊢÷+/)?⎕⍴0

Try it on APLgolf!

A tradfn submission which prints the list and returns the sum.

                  ⎕⍴0 ⍝ create a vector with input-many 0's
                 ?    ⍝ for each 0, get a random number between 0 and 1
            ⊢÷        ⍝ divide each number by
              +/      ⍝ the sum of all numbers
         ⎕←           ⍝ print the resulting vector
   ⊢×                 ⍝ multiply the vector element-wise
     1∘⌽              ⍝ with the vector rotated to the left by 1
 +/                   ⍝ take the sum of all products

If appending the sum to the list is fine as output, this could be 20 bytes: x,+/x×1⌽x←(⊢÷+/)?⎕⍴0

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

R, 49 45 bytes

a=rexp(scan());a=a/sum(a);a;a%*%c(a[-1],a[1])

Try it online!

-4 bytes by Robin Ryder

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

JavaScript (ES6),  89  88 bytes

Returns [ array, sum ].

f=(n,a=[],t=s=0)=>n?f(n-1,[...a,v=Math.random()],t+v):[a.map(k=>(s+=v/t*(v=k),v/t)),s/t]

Try it online!

Commented

f = (                      // f is a recursive function taking:
  n,                       //   n = input
  a = [],                  //   a[] = array
  t =                      //   t = sum of non-normalized values
  s = 0                    //   s = sum of a[i] * a[(i + 1) mod n] / t
) =>                       //
n ?                        // if n is not equal to 0:
  f(                       //   do a recursive call:
    n - 1,                 //     decrement n
    [ ...a,                //     pass a new array with all previous elements of a[]
      v = Math.random() ], //     followed by a new random value v in [0,1)
    t + v                  //     add v to t
  )                        //   end of recursive call
:                          // else:
  [                        //   build the answer array:
    a.map(k =>             //     for each value k in a[]:
      ( s +=               //       add to s:
          v / t            //         the previous normalized value v / t,
          * (v = k),       //         multiplied by k (and update v to k)
        v / t              //       yield the normalized value
      )                    //
    ),                     //     end of map()
    s / t                  //     also return the normalized sum
  ]                        //   end of answer array
\$\endgroup\$
4
  • \$\begingroup\$ The result seems wrong. Notice that your sum of products should be s / t / t, because s is a quadratic expression. \$\endgroup\$ Feb 17 at 0:26
  • \$\begingroup\$ @SketchySketch s is the sum of a[i-1] / t * a[i], so we only need to divide once by t at the end of the process. \$\endgroup\$
    – Arnauld
    Feb 17 at 0:29
  • \$\begingroup\$ Oh sorry, missed that. \$\endgroup\$ Feb 17 at 0:32
  • \$\begingroup\$ @SketchySketch Here is some extra code to double-check the result. \$\endgroup\$
    – Arnauld
    Feb 17 at 0:36
2
\$\begingroup\$

Julia, 46 bytes

n->(a=rand(n);a/=sum(a))=>a[2:end]'*a[1:end-1]

Try it online!

returns array => sum

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

Wolfram Language (Mathematica), 42 bytes

{##2,#}&@@#.#|#&[#/Tr@#&@RandomReal[1,#]]&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 25 bytes

FN⊞υ‽φ≧∕Συυ⊞υΣEυ×ι§υ⊕κI⮌υ

Try it online! Like the 05AB1E answer, I generate n random numbers between 0 and 999, then scale them so their sum is 1. A larger range could be obtained at the cost of one or two bytes. Also, it's unclear whether the sum has to be first; printing it last would save two bytes. Explanation:

FN

Repeat n times...

⊞υ‽φ

... push a random integer to the predefined empty list.

≧∕Συυ

Divide the list by its sum.

⊞υΣEυ×ι§υ⊕κ

Multiply each element by its neighbour and push the sum to the list.

I⮌υ

Print the list in reverse so that the sum is first.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Given that OP linked to standard IO rules, I took that mean either order was ok. \$\endgroup\$
    – Jonah
    Feb 16 at 15:39
1
\$\begingroup\$

MathGolf, 11 bytes

ă]_Σ/∙╫m*Σ

Outputs the array and sum concatenated to one another.

Try it online.

Explanation:

Ä            # Loop the (implicit) input amount of times,
             # using a single character as inner code-block:
 ƒ           #  Push a random float in the range [0,1]
  ]          # Wrap all values on the stack into a list
   _         # Duplicate this list
    Σ        # Take the sum of it
     /       # Divide all values in the list by this sum
             # (so we now have a list of random values summing to 1)
      ∙      # Triplicate this list
       ╫     # Rotate the top copy once towards the left
        m*   # Multiply the top two lists position-wise together
          Σ  # Take the sum of that list
             # (after which the entire stack joined together is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

Python 3 + numpy, 75 bytes

from numpy import*
def f(n):x=random.rand(n);x/=sum(x);return x,x@roll(x,1)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

J, 30 27 25 bytes

-2 to thanks to ovs's rotate idea

[:(;1#.]*1|.])@(%+/)?@$&0

Try it online!

  • $&0 Duplicate 0 "input" times.
  • ?@ And "roll" for each (?0 produces a random number between 0 and 1).
  • [:...(%+/) Divide each by sum of all.
  • (;1#.]*1|.]) To that boxed list append ; the sum of 1#. the list ] times * the list rotated once to the left 1|.].
\$\endgroup\$
1
\$\begingroup\$

Python 3, 124 121 bytes

Saved a byte thanks to Kevin Cruijssen!!!
Saved 3 bytes thanks to Danis!!!

def f(n):l=[random()for i in[0]*n];l=[e/sum(l)for e in l];return l,sum(a*b for a,b in zip(l,l[1:]+l))
from random import*

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ using def instead of lambda would be a little shorter \$\endgroup\$
    – Danis
    Feb 16 at 16:55
  • \$\begingroup\$ tio.run/… \$\endgroup\$
    – Danis
    Feb 16 at 18:29
  • \$\begingroup\$ @Danis Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 16 at 19:47
1
\$\begingroup\$

05AB1E, 17 15 14 17 bytes

₄Ý.rI£DO/ÐÀ*O‚

Outputs as a pair [array, sum].

-2 bytes thanks to @Neil.
-1 byte by changing two explicit prints with enclose/overlap builtins =Ćü*O, to something similar as my MathGolf answer with pair and implicit print ÐÀ*O‚
+2 bytes so duplicated items are possible and +1 byte to maximize the amount of floats possible

Try it online (but uses [0,1000] instead of [0,9876543210] to speed things up a bit).

Explanation:

žmÝ               # Push a list in the range [0,9876543210]
   Iи             # Repeat it the input amount of times
                  # (so we can potentially get duplicated items)
     .r           # Randomly shuffle this list
       I£         # Only leave the first input amount of values
         D        # Duplicate this list
          O       # Sum them together
           /      # Divide all values by this sum
                  # (so we now have a list of random values summing to 1)
            Ð     # Triplicate this list
             À    # Rotate the top copy once towards the left
              *   # Multiply the top two lists position-wise together
               O  # Sum this list
                ‚ # Pair the list together with this sum
                  # (after which this pair is output implicitly as result)
\$\endgroup\$
7
  • 2
    \$\begingroup\$ I don't think you have to divide the list by 1000, since you're dividing all values by their sum anyway. \$\endgroup\$
    – Neil
    Feb 16 at 15:28
  • \$\begingroup\$ @Neil Ah of course. Thanks! :) \$\endgroup\$ Feb 16 at 15:32
  • \$\begingroup\$ Doesn't this have a zero probability of outputting a list with any equal elements? (...and also other lists which should have non-zero probability - or is 1000 big enough to produce all floats somehow?) Also what happens when n>1001? \$\endgroup\$ Feb 16 at 19:31
  • \$\begingroup\$ @JonathanAllan You're right about the first part, since I shuffle a list with unique values. I can fix that in two bytes by repeating the list the input amount of times before shuffling if necessary (is it necessary?). 05AB1E doesn't have any float random builtins, which is why I use this approach in the first place. If you look at my initial 17-byte version you can see I had ₄Ý₄/ and also added a comment about having more decimal digits by increasing that to let's say \$10^6\$ by adding two bytes. \$\endgroup\$ Feb 16 at 19:40
  • \$\begingroup\$ @JonathanAllan As for whether 1000 is big enough to produce all floats, I doubt it.. And increasing it to let's say 5000 should hold similar results I'm pretty sure, and the higher you go, the more unique floats become available I guess. The DO/ makes sure the floats will sum to 1. Do we know how accurate floats have to be for "By saying random, I mean, every array satisfying the requirements in 2 should have a non-zero probability of occurrence." to be true? \$\endgroup\$ Feb 16 at 19:41
1
\$\begingroup\$

MATL, 13 bytes

l&rts/ttlYS*s

Try it online!

Explanation

             % Implicitly retrieve input (N) as an integer
l            % Push the literal 1 to the stack
&r           % Create an N x 1 array of random floats
t            % Duplicate this array
s            % Sum the elements of this array
/            % And perform element-wise division of the original array by this sum
             % to get the array, A
tt           % Duplicate A (twice)
lYS          % Circularly shift A by 1 element
*            % Perform element-wise multiplication with A
s            % Compute the sum
             % Implicitly display A and the sum of the products
\$\endgroup\$
1
\$\begingroup\$

Ruby, 83 82 72 71 bytes

->n{k=(1..n).map{rand};p=k[~-s=0]/z=k.sum;[k.map{|x|s+=p*x/z;p=x/z},s]}

Try it online!

-4,-1,-6 from ASCII-only!

-4, shortening it further.

-1 more byte from ASCII-only.

\$\endgroup\$
10
  • \$\begingroup\$ Tried it online; the sum of your array doesn't seem to be 1. \$\endgroup\$ Feb 17 at 10:41
  • \$\begingroup\$ @SketchySketch fixed it \$\endgroup\$
    – Razetime
    Feb 17 at 10:44
  • \$\begingroup\$ why the *1.0? \$\endgroup\$
    – ASCII-only
    Feb 18 at 10:18
  • \$\begingroup\$ @ASCII-only Added it due to paranoia and forgot about it \$\endgroup\$
    – Razetime
    Feb 18 at 10:19
  • \$\begingroup\$ 82 \$\endgroup\$
    – ASCII-only
    Feb 18 at 10:29
0
\$\begingroup\$

Jelly, 18 bytes

No built-in for random floats, so half the code is that!

2ṗ⁹XHCḅ.)÷S$µṙ1ḋƊ,

A monadic Link accepting an integer, n, which yields a list containing a non-negative float (the sum of products) and the generated list of non-negative floats of length n which sums to 1.

Try it online! (Note that (\$256\$) has been replaced with 9 (\$9\$) for speed - generating all \$2^{256}\$ lists of bits would take a while. Using a number as big as \$256\$ is not necessary, it's just terse.)

How?

(Bug fixed above, will update this section later.)

Note: Uses 256 random bits to generate a random float in \$[0,1]\$.

2ṗ⁹XHCḅ.)µ÷Sṙ1ḋƊ, - Link: n
         )        - for each:
2                 -   2
  ⁹               -   256
 ṗ                -   (256) Cartesian product (2 implicitly -> [1,2])
   X              -   pick one at random        e.g.  [1,2,2,1, ... ,1,2]
    H             -   halve                           [0.5,1,1,0.5, ... ,0.5,1]
     C            -   complement                      [0.5,0,0,0.5, ... ,0.5,0]
       .          -   a half                          0.5
      ḅ           -   convert (list) from base (0.5)  a float in [0,1]
         µ        - start a new monadic chain         (call that x)
           S      - sum                               sum(x)
          ÷       - divide                            normalised(x)
               Ɗ  - last three links as a monad:      (call that Y=[y1,y2,...,yn])
                  -   one                             1
            ṙ     -   rotate left by (1)              [y2,...,yn,y1]
              ḋ   -   dot product (with Y)            y1.y2+y2.y3+...+yn.y1
                , - pair                              [y1.y2+y2.y3+...+yn.y1, Y]
\$\endgroup\$
2
  • \$\begingroup\$ Tried it online; the sum of your output array isn't 1. \$\endgroup\$ Feb 17 at 1:08
  • \$\begingroup\$ Oops, this should fix it. Will update the post later. Thanks for notifying! \$\endgroup\$ Feb 17 at 1:22

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.