As said before, this question actually doesn't have an answer: The restrictions imposed on the numbers make the randomness questionable at best.
However, you could come up with a procedure that returns a list of numbers like that:
Let's say we have picked the first two numbers randomly as -0.8 and -0.7. Now the requirement is to come up with 3 'random' numbers that sum up to 2.5 and are all in the range [-1,1]. This problem is very similar to the starting problem, only the dimensions have changed. Now, however, if we take a random number in the range [-1,1] we might end up with no solution. We can restrict our range to make sure that solutions still exist: The sum of the last 2 numbers will be within the range [-2,2]. This means we need to pick a number in the range [0.5,1] to make sure we can reach a total of 2.5.
The section above describes one step in the process.
In general: Determine the range for the next number by applying the range of the rest of the numbers to the required sum.
Pseudo-code:
function randomNumbers (number, range, sum) {
restRange = range * (number - 1)
myRange = intersection ([sum - restRange.upper, sum - restRange.lower], range)
myNumber = random(myRange)
rest = randomNumbers (number-1, range, sum - myNumber)
return [myNumber, rest]
}
So for the case described above
randomNumbers (3, [-1,1], 2.5)
restRange = [-1,1] * (3-1) = [-2,2]
myRange = intersection ([2.5-2,2.5-(-2)], [-1,1]) = intersection ([0.5,4.5],[-1,1]) = [0.5,1]
A quick-and-dirty implementation in Java:
public class TestRandomNumberList
{
@Test
public void test()
{
double[] numbers = new double[5];
randomNumbers(numbers, 0, -1, 1, 1);
assertEquals(sum(numbers), 1.0, 0.00001);
for (double d : numbers)
{
assertTrue(d >= -1 );
assertTrue(d <= 1);
}
}
private void randomNumbers(double[] numbers, int index, double lowerBound, double upperBound, double sum)
{
int next = index + 1;
if (next == numbers.length)
{
numbers[index] = sum;
}
else
{
int rest = numbers.length - next;
double restLowerBound = lowerBound * rest;
double restUpperBound = upperBound * rest;
double myLowerBound = Math.max(lowerBound, sum - restUpperBound);
double myUpperBound = Math.min(upperBound, sum - restLowerBound);
numbers[index] = random(myLowerBound, myUpperBound);
randomNumbers(numbers, next, myLowerBound, myUpperBound, sum - numbers[index]);
}
}
private double random(double myLowerBound, double myUpperBound)
{
double random = Math.random();
return myLowerBound + random * (myUpperBound - myLowerBound);
}
private double sum(double[] numbers)
{
double result = 0;
for (double num : numbers)
{
result += num;
}
return result;
}
}
First create the list of numbers to check based on the initial number.
Example: 253
Assume split only once.
The Numbers From the initial number: [2,53], [25,3]
Note, one could do some de-duping here as well to avoid double processing the same number (Example: 111 only has two numbers 1, 11).
Each of these "split pair" can be checked if each number is prime.
If (IsPrime(2) and IsPrime(53)) => then true
If (IsPrime(25) and IsPrime(3)) => then false (25 is not prime)
So, just send each number to your IsPrime() number sieve. (Eratosthenes, etc.) In this case the numbers to check for prime are 2,53,25,3. Then "And Logic Gate" each split pair for the final answer. One could parallelize IsPrime() for multiple number processing at the same time.
There are some shortcuts. If the original number ends in 4,6,8, or zero, any "split pair" will always evaluate to false since one of the numbers in the pair is even and never prime. (@Andres F., @user949300) So, one could do that check first rather than running all the numbers through the sieve as a short circuit to save CPU. I'm sure there are some other tricks as well.
Best Answer
I just wrote an implementation in Clojure, a functional Lisp-I, which you may find below. Because of the controversy in the commments to this answer, I will try to explain the code and the techniques used to achieve the result as good as possible, especially for those who are not Clojurists. Forgive me if I don't touch on everything in great detail and length.
This version does not mutate state. All of Clojures values are immutable, e. g. a vector [1 2] can not be altered once it has been constructed. When you want to concat that vector with another vector [3 4] you may invoke a function like concat like this
(concat [1 2] [3 4]). Concat will return a new vector [1 2 3 4] and the two input vectors will be forgotten. The great thing is that behind the scenes, structural sharing is happening: The new vector [1 2 3 4] consists of the same data [1 2] and [3 4] consisted of. Also, if we had bound the vector [1 2] to a symbolainstead, after(concat a [3 4])a would still be [1 2]. So while you are always generating new immutable values, in memory only the delta will be allocated.One other feature of Clojure I am taking advantage of is laziness. E. g. you can build a sequence of all number 0 ... n with
(range). The call to range returns an infinite sequence like(0 1 2 3 4 5...), but it is not realized until elements of it are consumed. Finally, many transformation functions return new lazy-sequences from lazy input sequences, so(filter even? (range))would give me a lazy sequence of all numbers >= 0 for which the predicate even? (a boolean function) returns true - however, the filtering only happens when I actually consume elements from that sequence, e. g.(take 3 (filter even? (range)))will return(0 2 4): Until here, filter has been invoked five times (as many times as necessary to produce three elements or have the input sequence consumed).The prime ring generator below utilizes this laziness. If you invoke
(rings-of-primes 100)it immediately returns a lazy sequence of all possible prime rings with 100 elements from 1 to 100. Nothing is calculated, so if I wanted to have only three rings, I could do(take 3 (rings-of-primes 100))and calculation would only happen for the production of three rings.The core to the solution below is the function
helper-fnwhich is defined withinrings-of-primes. It takes two immutable values as arguments and refers to two other immutable values,length(the argument torings-of-primes) andn-range(defined inrings-of-primesas seq [1 .. length]) in its body.The two arguments to helper-fn are
used, an immutable set of numbers that have been used in the possible ring passed as the second arg,acc(short for accumulator).One of the great advantages of Clojure is that when you are dealing with immutable values, it's quite easy to write pure functions.
helper-fnis one of those pure functions. It is defined as follows: It takes the input of a set of used numbers, and a vector of numbers which is supposed to be a partial ring of primes, and always returns a sequence of possible rings of primes that begin with the numbers inaccand have a size oflength. If no rings are possible,helper-fnreturns(), an empty list (not the same asnilin Clojure).In the above code-snippet (the first lines of
helper-fn), the symbollast-elemis bound to the last value ofacc. Then within the conditional statementiftwo conditions are tested: 1. Has accumulator the user-desired length ((= length (count acc)))?, 2. Do the last and the first element add up to a prime number. If both conditions are matched, helper-fn returns[acc], a vector with exactly one element: The accumulator, a valid prime-ring. The nesting in an additional vector is needed because our function is supposed to return a sequence of valid prime-rings, not just a sequence of numbers.Now what happens if the passed value is not a prime-ring, like when the function is invoked the first time within
rings-of-primes:(helper-fn #{1} [1]). As you might have noticed, #{1} is the notation for a set, and within helper-fn,usedwill now be bound to #{1} andaccwill be bound to [1].Given that we have asked for a
lengthof 4, the test-clause in the code snippet above will fail. What happens then?The
parity-filtersymbol will be bound to either the predicate function odd? or to the predicate function even?, depending on whether the last-element ofaccis even or odd. The reason is that you can divide even numbers by two, and adding two even numbers or two odd numbers always results in an even number which can't be a prime number then. So we only want the numbers with the opposite parity of the last element ofacc,last-elem.->>is an awesome macro. It does not do anything except for reordering the code you put into it. That is one of the advantages of Clojure being a lisp, that all your code is data that can be manipulated before evaluation.->>reorders your code so(->> x (doY) (doZ baz))=>(doZ baz (doY x)). In other words, the first argument is appended to the end of the second form, which is appended to the end of the third form and so on.So in this case, n-range, which was generated at the beginning of
rings-of-primes, another immutable value, will be threaded with->>.n-rangewill always be a sequence [1 ..length]. Now this sequence must be filtered. We define a small function, a lambda, on the fly as the first argument to filter:In this case #(...) creates a function with one argument to which we refer as %. E. g.
#(+ % %)would create a function that takes one argument and doubles it. Our lambda is a predicate function that tests the argument for three conditions: 1. It must pass the parity-filter, 2. It may not be in the set used (you can invoke sets like functions and they return whether they contain the argument), 3. Added to the last-elem of acc, it must be a prime-number. If this three conditions match, it is a possible candidate for the next iteration of the prime ring we are building, and it will be part of the lazy sequence returned by thefilterexpression.After that, a function
lazy-mapcatthat comes with this source, is invoked. It takes a transformation function and a sequence of elements (our filtered candidates), transforms each input element with the transform function and concats the returned value (a sequence) to the other returned values. The transformation function may return any kind of sequence, also the empty sequence. Let's have a closer look at the transformation function:Yes! It's a call to helper-fn itself.
conjtakes a collection and an argument and returns a new collection with that argument in it. Here we put the value taken from our filtered sequence into a new version ofused, also create a new version ofaccwith that number in it, and pass them to helper-fn. Now go back to line 1.helper-fnwill then (after many more recursive steps) return a sequence of possible prime-rings and because ofmapcatwe do that for each candidate that may be the next valid number in the current prime-ring. All the resulting sequences of rings will be concatenated to one sequence of rings. Of course, in some caseshelper-fnwill return an empty list, and on a higher level, that empty list will be concataned with other lists - also within a mapcat expression.As you can see, no state is mutated. The resulting function is pure and can also be invoked with odd lengths or negative input values, in which case it will (mathematically correctly) return an empty list as a result.
You could say that the backtracking happens with
accpassed to helper-fn, but much more I'd like to think of this implementation of a pure function call that results in the self assembly of possible prime-rings through a series of recursive function calls.