My Math Forum Is there a (nt) theorem that could help with this?

 Number Theory Number Theory Math Forum

 August 11th, 2018, 06:01 PM #1 Newbie   Joined: Aug 2018 From: CT Posts: 1 Thanks: 0 Is there a (nt) theorem that could help with this? 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! Last edited by skipjack; August 12th, 2018 at 12:32 AM.
 August 12th, 2018, 08:49 AM #2 Senior Member   Joined: May 2016 From: USA Posts: 1,084 Thanks: 446 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. Last edited by JeffM1; August 12th, 2018 at 08:55 AM.
August 12th, 2018, 10:00 AM   #3
Math Team

Joined: Oct 2011

Posts: 12,904
Thanks: 883

Quote:
 Originally Posted by mollyloveblue2002 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.
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

 August 12th, 2018, 10:54 AM #4 Senior Member   Joined: May 2016 From: USA Posts: 1,084 Thanks: 446 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.
August 12th, 2018, 11:58 AM   #5
Math Team

Joined: Oct 2011

Posts: 12,904
Thanks: 883

Quote:
 Originally Posted by JeffM1 Denis If I am interpreting the problem correctly, the listed integers are not necessarily sorted in ascending order,....
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!) ?

August 12th, 2018, 12:33 PM   #6
Senior Member

Joined: May 2016
From: USA

Posts: 1,084
Thanks: 446

Quote:
 Originally Posted by 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!) ?
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.

 Tags divisors, gcd, theorem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Schwhat Calculus 4 November 22nd, 2016 01:58 PM djcan80 Calculus 2 August 24th, 2016 07:28 PM jenny15 Algebra 1 December 1st, 2015 09:49 AM righen Algebra 3 January 23rd, 2014 08:19 AM george gill Calculus 5 May 14th, 2011 02:13 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top