2
$\begingroup$

I have five 10 sequences of 14 numbers each:-

1. 0, 22, 33, 55, 65, 76, 96, 99, 116, 137, 147, 157, 178, 184
2. 10, 20, 29, 53, 60, 77, 97, 100, 117, 138, 148, 154, 171, 191
3. 8, 20, 37, 55, 58, 70, 96, 101, 119, 137, 144, 155, 173, 192
4. 8, 19, 37, 43, 62, 70, 96, 108, 119, 129, 151, 156, 172, 195
5. 13, 21, 33, 44, 64, 80, 87, 107, 118, 127, 151, 154, 180, 186
6. 5, 27, 39, 48, 60, 72, 96, 101, 119, 136, 141, 163, 168, 190
7. 3, 21, 37, 44, 61, 83, 95, 98, 124, 130, 146, 162, 178, 183
8. 5, 17, 41, 46, 64, 82, 84, 105, 123, 128, 146, 163, 169, 192
9. 9, 18, 38, 43, 59, 81, 86, 105, 124, 132, 140, 167, 173, 190
10. 8, 18, 37, 54, 62, 72, 95, 103, 113, 139, 150, 157, 175, 182

These sequences are randomly generated from a program, which identifies a information contained in a file.

at first glance these seems to be random.But I am able to figure out some similarity between them. Like:-

a. Sum of each sequences is 1365.

b. There are always 14 numbers and these lies between 0 and 195
   (square of 14 minus 1).

c. The first number of the series lies between 0 and 13 (14-1) and all 
   the next numbers lies the chunk of 14 numbers like next number
   always lies between 14-27, third one between 28-41 and so on.

After all these observations I want to generate these sequences logically with the help of some formula. I don't now which formula to use? given the first number of the sequences and generate the rest so that sum of the 14 digits is 1365.

I need your help in understanding relationship between these sequences, relationships between each number of series and generate them with some formula.

I want to generate all the sequences which satisfy such criteria and store them in some sort of database for future matching of file information.

As per my understanding this some sort of choice based sequence like if I choose 8 the next number I can choose is 18,19, 20 and if I choose 19 I have different choices or if choose 20 I have different choices and so on but still each number lies in chunk of 14 and sum of series is 1365.

Please ask me more information if required.

Any sort of help or hint is appreciated.

$\endgroup$
  • $\begingroup$ @Théophile question updated. $\endgroup$ – Sachin Singh Sep 21 '17 at 16:20
  • 1
    $\begingroup$ Note that $$1365 = 6.5 + (6.5+14) + (6.5+28) + \cdots + (6.5+182),$$ i.e., it is expected sum of numbers chosen uniformly at random from the given ranges. $\endgroup$ – Théophile Sep 21 '17 at 16:24
  • $\begingroup$ Now, could you explain more clearly what you're looking for? It's easy to generate these sequences (for example, just choose numbers alternately $.5$ below or above the averages: $(6,21,34,\ldots,189)$), but do you want to generate all such sequences? Do you want to generate them randomly? If randomly, then uniformly at random? $\endgroup$ – Théophile Sep 21 '17 at 16:30
  • $\begingroup$ @Théophile they may be random but they should be in chunk of 14. $\endgroup$ – Sachin Singh Sep 21 '17 at 16:37
  • 2
    $\begingroup$ There's more to these sequences: if we write $x_i = 14 \cdot i + y_i$, then $(y_i)_{0 \leqslant i < 14}$ is always a permutation of $\{ 0, 1, \ldots, 13 \}, $ namely: $$\begin{array}{rrrrrrrrrrrrrr} 0 & 8 & 5 & 13 & 9 & 6 & 12 & 1 & 4 & 11 & 7 & 3 & 10 & 2 \\ 10 & 6 & 1 & 11 & 4 & 7 & 13 & 2 & 5 & 12 & 8 & 0 & 3 & 9 \\ 8 & 6 & 9 & 13 & 2 & 0 & 12 & 3 & 7 & 11 & 4 & 1 & 5 & 10 \\ 8 & 5 & 9 & 1 & 6 & 0 & 12 & 10 & 7 & 3 & 11 & 2 & 4 & 13 \\ 13 & 7 & 5 & 2 & 8 & 10 & 3 & 9 & 6 & 1 & 11 & 0 & 12 & 4 \end{array}$$ $\endgroup$ – Adayah Sep 21 '17 at 17:03
1
$\begingroup$

To generate all such sequences, first generate all permutations of $[0,13]$ (from @Adayah's observation in the comments above). There are $14!=87,178,291,200$ such permutations, so this may take some time and will use up a good deal of storage space.

Then add $(0,14,28,\ldots,182)$ to each sequence to bring the numbers into the desired range.

If you're just interested in seeing whether a certain sequence $s$ has the desired property, then it suffices to check that $s - (0,14,28,\ldots,182)$ is a permutation of $[0,13]$.

$\endgroup$
  • $\begingroup$ I have a program for that, but there is a concern of time and efficiency. it takes a lot of time to execute. Hence I was looking for some mathematical formula. $\endgroup$ – Sachin Singh Sep 21 '17 at 16:47
  • $\begingroup$ 1 this is a sequence not a series. and 2@SachinSingh there are many sequences to generate even if you take nanoseconds to generate each one , it will add up to 15034302060637734370093170532.411179780 seconds. that's just from knowing how many positive partitions there are of 1365 ( used PARI/GP). edit: okay that reduces some with only certain limitations but it adds up quickly still. $\endgroup$ – user451844 Sep 21 '17 at 16:59
  • $\begingroup$ @RoddyMacPhee Thanks; updated. $\endgroup$ – Théophile Sep 21 '17 at 17:30
  • $\begingroup$ @Théophile have you taken modular constraints into the situation ? that may reduce your storage etc ( as my answer shows). $\endgroup$ – user451844 Sep 21 '17 at 19:55
  • $\begingroup$ @RoddyMacPhee Yes, that is precisely what $14!$ represents. $\endgroup$ – Théophile Sep 21 '17 at 22:39
0
$\begingroup$

here's a way to cut down your work (even using condition c we have about $11112006825558016=14^{14}$, sequences) use the fact that only if there are an odd number of odd values will the sum be odd ( via odd+odd=even and such, aka a parity argument). Since there are at most 7 odd numbers in each range this cuts the number of sequences to check down significantly ( down to $7^{15}=4747561509943$ I think). oh and the PARI/GP console + GP2C compiler may help.

$\endgroup$
  • $\begingroup$ That's a neat trick actually, there would have to be an odd number of odd numbers, while the rest are even, to be able to get an odd number. $\endgroup$ – Sam Anderson Sep 21 '17 at 18:04
  • $\begingroup$ and it cuts down the time @SamAnderson even at a nanosecond per sequence the sequences condition c works for, would take about a 3rd of a year to generate. by comparison the reduced number of sequences looked at ( okay you still have to get data for them all) may take as little as ~1.5 hours to generate them all. $\endgroup$ – user451844 Sep 21 '17 at 18:07
  • $\begingroup$ @SamAnderson we can use the same thing mod 3 and mod 5 etc. that would decrease it again if 1 and 4 mod 5 ( as well as 2 and 3 as a pair) aren't equal then there's no way the sum can be a multiple of 5 ( which 1365 is). $\endgroup$ – user451844 Sep 21 '17 at 18:26
  • $\begingroup$ okay I guess the differences of each pair could cancel. $\endgroup$ – user451844 Sep 21 '17 at 18:53
0
$\begingroup$

This seems to be an NP-problem, there's information here that we can't know (i.e. the values of random numbers, before we've actually drawn them). Nonetheless I will give you an incomplete formula, but remember that probably the only way to do this is to brute-force it in non-polynomial time. Something like: generate 14 numbers, check IF they follow all constraints, if they do, we have a sequence, else we just try again and again and again until we're successful.

For a sequence: $$t_1 + t_2 + t_3 + \ ... \ + t_{14} = 1365$$

We have that: $$14(n-1)\leq t_n \leq 14n -1 \tag{1}$$

So the strategy would be to check that $(1)$ with $n=1$ (first term) is satisfied, then check that it's satisfied with $n=2$ etc. all the way up to $n=14$.

The main problem here, which makes be strongly believe that it is an NP-problem, is that although the constraint $(1)$ isn't hard to account for; the constraint that all terms have to sum to $1365$ in the end is impossible to account for with respect to $(1)$. Because $(1)$ is where we're actually generating the terms! Which of course means that if we want to account for the $sum = 1365$ constraint as well, then we have to know what the random terms are before they're even generated. So if my reasoning is correct then it's impossible.

It's possible to at least do it a bit better than a brute-force tactic by having something like: if the generated terms sum up to $1365$ before we've reached the end just start again, this will remove some time at least. We can use many more tricks most likely, but the computational time will still be rather hard to handle no matter what.

$\endgroup$
  • $\begingroup$ To go this way, it is best to keep track of the total deviation as you go. That way you can prune branches that cannot possibly add up to $1365$. But even so, it is computationally infeasible to write out all such sequences. $\endgroup$ – Théophile Sep 21 '17 at 17:50
  • $\begingroup$ You need to prune well before the terms sum up to $1365$, because you'll be adding a minimum of $0,14,\ldots,140,154,168,182$ at each step. $\endgroup$ – Théophile Sep 21 '17 at 17:53
  • $\begingroup$ @Théophile Yes I agree, the problem seems to be rather hard to actually handle. Even by brute-forcing it it would be ridiculous. I strongly believe though that it is the only way. $\endgroup$ – Sam Anderson Sep 21 '17 at 17:53

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.