
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 11th, 2018, 07: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 bruteforcing 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 theorybased 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 32bit 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 01:32 AM. 
August 12th, 2018, 09:49 AM  #2 
Senior Member Joined: May 2016 From: USA Posts: 1,306 Thanks: 549 
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, restart loop 1 with q incremented by 1. If no, run loop 2 (midlevel loop) and then restart 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, restart 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 lessthan test is almost certainly considerably more efficient than the evenlydivides test.) If integer in position r is not evenly divisible by integer in position q, restart 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 restart 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, restart 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 restart 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 09:55 AM. 
August 12th, 2018, 11:00 AM  #3  
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,985 Thanks: 995  Quote:
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, 11:54 AM  #4 
Senior Member Joined: May 2016 From: USA Posts: 1,306 Thanks: 549 
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, 12:58 PM  #5 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,985 Thanks: 995  
August 12th, 2018, 01:33 PM  #6  
Senior Member Joined: May 2016 From: USA Posts: 1,306 Thanks: 549  Quote:
You seemed to me in your examples to be ordering the list.  

Tags 
divisors, gcd, theorem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Rolle's Theorem vs Mean Value Theorem  Schwhat  Calculus  4  November 22nd, 2016 02:58 PM 
Stokes's Theorem and Green's Theorem  djcan80  Calculus  2  August 24th, 2016 08:28 PM 
Remainder theorem and factor theorem  jenny15  Algebra  1  December 1st, 2015 10:49 AM 
Remainder Theorem + Factor Theorem  righen  Algebra  3  January 23rd, 2014 09:19 AM 
proof by using greens theorem or stokes theorem  george gill  Calculus  5  May 14th, 2011 03:13 PM 