![]() |
|
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 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 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, 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 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 | |
|
![]() | ||||
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 |