February Number Challenge

[SMcNeill]

Let me give you an example of a number that meets the criteria that I was looking for:

1234567818 = 2 * 31 * 1991239 -- only 3 unique primes which are the factors of the number.  (Of course 62 is a factor as well, but I didn't count it as I was breaking things down to search for the base primes for my solution, which, as I mentioned above, is quite a bit different that the problem that was apparently supposed to be solved.)

There's also numbers like 1234567812, which is 2 * 2 * 30864203, but it may not count as a solution as it doesn't have three distinct factors (2 is there twice, so it's not 3 unique numbers).

Needless to say, what I was working up takes just a wee bit longer to process and generate than a list for 4th roots, but it certainly makes more sense in the concept of storing and sorting the values of the factors.  With n ^ 4, as long as you run a loop from 1 to n, it's already sorted for you...

[SMcNeill]

This looks like the solution to the problem you presented (I think, if we're interpreting the question properly):

Code: QB64: [Select]

1. DefLng A-Z
2. For i = 101 To 199 Step 2 'can remove all factors of 2 by default
3.     If i ^ 4 >= 123456789 And i ^ 4 <= 223456789 Then
4.         For j = 3 To Sqr(i) Step 2
5.             If i Mod j = 0 Then Exit For 'not a primt
6.         Next
7.         If j > Sqr(i) Then Print i, i * i, i * i * i 'only prime numbers can be the solution.  Others have more factors and don't qualify.
8.     End If
9. Next

(As to why I limited my run from 100 to 200. it's because 100 ^ 4 is a 9 digit number, and 200 ^ 4 is a 10 digit number, making those both larger than our bounds.  100000000 is less than 123456789, and 16000000 is greater than 223456789. They were just arbitrary values which I mind quickly recognized as being beyond our limits, so I lazily plugged them in for testing and results.)

[bplus]

Yes, those answers match the ones I got.

Here is how I worked it out:

Here is the code I started testing for the Challenge:

Code: QB64: [Select]

1. DefLng A-Z
2. For i = 123456789 To 223456789
3.     Locate 1, 40: Print i ' <<< progress report OMG! This is going to take far too long for 123456789+ numbers
4.     test = ThreeDivisors&(i)
5.     If test Then
6.         row = row + 1
7.         Locate row, 1
8.         For j = 2 To i / 2 'show divisors
9.             If i Mod j = 0 Then 'j divides i
10.                 Print j;
11.             End If
12.         Next
13.         Print " divides"; i
14.     End If
15. Next
16. Locate row + 1, 1
17. Print "End of run."
18. Sleep
19.  
20. Function ThreeDivisors& (n)
21.     For i = 2 To n / 2 ' count divisors
22.         If n Mod i = 0 Then 'i divides n
23.             count = count + 1: lastDivisor = i
24.             If count > 3 Then Exit Function ' too  many divisors
25.         End If
26.     Next
27.     If count = 3 Then ThreeDivisors& = lastDivisor
28. End Function

WTH? If this does 10 integers a second 100,000,000 integers will take
10,000,000 secs
=166,666 mins
=2777 hours
=115 days     Yikes! what's going on?


OK just try the code starting at the start and see what's going on:

Code: QB64: [Select]

1. DefLng A-Z
2. For i = 2 To 100000
3.     Locate 1, 40: Print i ' <<< progress report OMG! This is going to take far too long for 123456789+ numbers
4.     test = ThreeDivisors&(i)
5.     If test Then
6.         row = row + 1
7.         Locate row, 1
8.         For j = 2 To i / 2 'show divisors
9.             If i Mod j = 0 Then 'j divides i
10.                 Print j;
11.             End If
12.         Next
13.         Print " divides"; i
14.     End If
15. Next
16. Locate row + 1, 1
17. Print "End of run."
18. Sleep
19.  
20. Function ThreeDivisors& (n)
21.     For i = 2 To n / 2 ' count divisors
22.         If n Mod i = 0 Then 'i divides n
23.             count = count + 1: lastDivisor = i
24.             If count > 3 Then Exit Function ' too  many divisors
25.         End If
26.     Next
27.     If count = 3 Then ThreeDivisors& = lastDivisor
28. End Function
29.  

OH! We just need the first 4 powers of prime numbers !!!
because the divisors of i^4 are i, i^2 and i^3 easy!

OK so which integers to the 4th power lay between 123456789 and 223456789?
I ran this code:

Code: QB64: [Select]

1. DefLng A-Z
2. ' what is the first integer ^ 4 >= 123456789
3. i = 2
4. While i ^ 4 < 123456789
5.     i = i + 1
6. Wend
7. a = i ^ 4
8. Print i, a
9.  
10. ' what is the last integer i st i ^ 4 <= 223456789
11. While i ^ 4 <= 223456789
12.     i = i + 1
13. Wend
14. 'Ok backup i by 1
15. a = (i - 1) ^ 4
16. Print i - 1, a
17.  
18.  

'OK all i need are primes between 106 and 122!!!

Wow did that simplify our search for 3 divisors between 123456789 and 223456789

Final code:

Code: QB64: [Select]

1. DefLng A-Z
2. For n = 106 To 122 ' n^4 > 123456789 and n^4 < 223456789
3.     'if n is prime print the divisors
4.     Prime = -1
5.     For j = 2 To Sqr(n)
6.         If n Mod j = 0 Then Prime = 0: Exit For
7.     Next
8.     If Prime Then Print n; ", "; n ^ 2; ", "; n ^ 3; " divide"; n ^ 4
9. Next
10. 'verify my choice of n stop
11. Print
12. Print "Is 122 really the highest integer st i ^ 4 < 223456789 ?"
13. a = 122 ^ 4 ' is 122 really the highest value < 223456789 ?
14. b = 123 ^ 4
15. Print "122 ^ 4 ="; a; " Is this <= 223456789  "; a < 223456789
16. Print "123 ^ 4 ="; b; " Is this <= 223456789  "; b < 223456789
17.  
18.  

[SMcNeill]

But I still have the question of:  "What's the point of sorting, if that's the solution?"

For each found number, write down its largest nontrivial divisor in the answer. Arrange the answers in ascending order.

If sorting is going to be part of the problem, then I think my solution to break things down to base factors makes more sense. 

123456812 = 2 * 2 * 30864203
123456818 = 2 * 31 * 1991239

3 base factors (lowest common denominators), excluding the 1 and number itself, and with an order which would need storing and sorting.

Are you certain n ^ 4th is actually what we're supposed to be looking for here?  The sorting seems irrelevant if it is.

[bplus]

But I still have the question of:  "What's the point of sorting, if that's the solution?"

Quote
For each found number, write down its largest nontrivial divisor in the answer. Arrange the answers in ascending order.

Typical Russian Red Herring. :)  tsh73 teaches Computer Science in Russia, his English pretty good but some concepts hard to translate surely.

Remember we are talking Divisors of a number not factors or elements of the Divisors. (I think.)

[_vince]

I found this at Liberty Basic Forum (Feb 8) and so far nobody there has figured it out.

I just did but let's see if someone else can here at this forum:

tsh73

Who is the best programmer there? tsh, Rod, or technotitlick?

[bplus]

see Discord PM

[SMcNeill]

Who is the best programmer there? tsh, Rod, or technotitlick?

ME, of course!   😂😂

[_vince]

wow Steve, you also program in Liberty BASIC?

[SMcNeill]

wow Steve, you also program in Liberty BASIC?

Nope.  Never heard of it.  I'm just >THAT< good!  😁