mollyloveblue2002

Hello! I'm new here. First post!

I am working on writing a python program that solves the problem explained below. Unfortunately, all of the solutions I (and my Stack Overflow friends) have been able to come up with are just variations on brute-forcing it through either list comprehensions or nested for loops/if statements (https://stackoverflow.com/questions/...-comprehension).

My elementary number theory senses are tingling from 8 years ago, and I feel like there's some sort of number theory-based theorem that could be the key. I'm not looking for a python solution, but something that could point me in the right direction mathematically, that I will later be able to implement in Python (v 2.**)

Okay, here's the problem:
------------------------------------
Def: A "lucky triple" is a tuple (x, y, z) where x divides y and y divides z, such as (1, 2, 4).

Problem: Write a (python) function answer(L) that takes a list of positive integers L and counts the number of "lucky triples" of (Li, Lj, Lk) where the list indices meet the requirement i < j < k. The length of l is between 2 and 2000 inclusive. The elements of L are between 1 and 999999 inclusive. The answer fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0.

For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the answer 3 total, while [1,1,1] has only 1 triple, so the answer is 1.

--------------------------------------

Thank you in advance!

JeffM1

This is not a mathematical answer particularly, and I have not done serious coding in 50 years. But I think you may be missing a programming trick.

Let p be the number of elements in the original list.

Initiate counter A at zero.

Run loop 1 (the outer loop) with index q running from 1 through p - 2. First, test the integer in position q for zero. If yes, re-start loop 1 with q incremented by 1. If no, run loop 2 (mid-level loop) and then re-start loop 1 with q incremented by 1.

Loop 2 initiates index r at q + 1 and runs through p - 1. If integer in position r is less than integer in position q, re-start loop 2 with r incremented by 1. (If a < b, then b does not divide a evenly (that is math if you like), and the less-than test is almost certainly considerably more efficient than the evenly-divides test.) If integer in position r is not evenly divisible by integer in position q, re-start loop 2 with r incremented by 1. Otherwise, initiate counter B to zero and run loop 3 (the innermost loop). If counter B is zero, replace the integer in position r with zero and then re-start loop 2 with r incremented by 1. If counter B is not zero, add counter B to counter A.

Once you are in loop 3, you know that the integer in position q divides evenly into the integer in position r and that q < r. Loop three is indexed by s and starts at r + 1 and runs through p. If integer in position s is less than integer in position r, re-start loop 3 with s incremented by 1. If the integer in position r does not divide evenly into the integer in position s, restart loop 3 with s incremented by 1. Otherwise, add 1 to Counter B and re-start loop 3 with s incremented by 1.

The replacement by zero of the integer in position r if it is evenly divisible by any integer with a position less than r and does not evenly divide any integer with a position greater than r prunes the tree as it is being searched, and the testing for zero and for less than is more efficient than testing for even divisibility. If a great many of the numbers in the list divide evenly into others, there is a lot of search required whatever you do. If, however, many of the numbers are relatively prime, pruning while searching will substantially reduce the number of searches required.

It may be possible to search in a way that permits even more efficient pruning. I last coded in 1969 so I am very rusty indeed.

Denis

I'm getting a headache...are following 2 examples correct?
i,j,k
1,2,4
1,2,6
1,2,8
....
1,2,999994
1,2,999996
1,2,999998
Total: 499999

1,3,6
1,3,9
1,3,12
....
1,3,999993
1,3,999996
1,3,999999
Total: 333333

JeffM1

Denis

If I am interpreting the problem correctly, the listed integers are not necessarily sorted in ascending order, may or may not be duplicated, and each may be any one of the integers may range from 1 through 999,999.

In other words, there are 999,999^2000 possible lists, a rather large search universe. Of course we only have to search one list, but we know virtually nothing about it. The number of jolly triples is admittedly much smaller: if 2 precedes 6 and 6 precedes 18 in the list, that gives us one, but any other listed order of those same three numbers does not.

The question as I understand it is to find an algorithm that will say how many jolly triples there are in an arbitrary list efficiently.

Denis

Hmmm....OP states:
"the list indices meet the requirement i < j < k"

What am I misreading (I seem to be doing a lot of that!) ?

JeffM1

If 2 is in the 199th position, its index is 199. If 6 is in position 1000, its index is 1000. And if 18 is in position 2000, then 199 < 1000 < 2000 and 2 divides 6 and 6 divides 18.

You seemed to me in your examples to be ordering the list.