My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
mollyloveblue2002 is offline  
 
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.
JeffM1 is offline  
August 12th, 2018, 10:00 AM   #3
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 12,904
Thanks: 883

Quote:
Originally Posted by mollyloveblue2002 View Post
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
Denis is offline  
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.
JeffM1 is offline  
August 12th, 2018, 11:58 AM   #5
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 12,904
Thanks: 883

Quote:
Originally Posted by JeffM1 View Post
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!) ?
Denis is offline  
August 12th, 2018, 12:33 PM   #6
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,084
Thanks: 446

Quote:
Originally Posted by Denis View Post
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.
JeffM1 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 01:58 PM
Stokes's Theorem and Green's Theorem djcan80 Calculus 2 August 24th, 2016 07:28 PM
Remainder theorem and factor theorem jenny15 Algebra 1 December 1st, 2015 09:49 AM
Remainder Theorem + Factor Theorem righen Algebra 3 January 23rd, 2014 08:19 AM
proof by using greens theorem or stokes theorem george gill Calculus 5 May 14th, 2011 02:13 PM





Copyright © 2018 My Math Forum. All rights reserved.