Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: bplus on February 11, 2022, 02:14:18 pm

Title: February Number Challenge
Post by: bplus on February 11, 2022, 02:14:18 pm
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
Quote

It is high-school test problem my kid got yesterday
I jumped in - but after getting something working... I Googled and it happened that I solved quite anoter task (Doh).

So here is it (Google-translated text, original is in Russian)
Let's call a nontrivial divisor of a natural number its divisor, which is not equal to one and the number itself. For example, the number 6 has two nontrivial divisors: 2 and 3. Find all natural numbers belonging to the segment [123456789; 223456789] and having exactly three nontrivial divisors. For each found number, write down its largest nontrivial divisor in the answer. Arrange the answers in ascending order.


Could you solve it without Google?

I couldn't solve it with Google only learned that non trivial divisor is not the same as a proper divisor.

I tried brute force but that was going to take hours, no there is a little thing you have to discover then easy as pie.

It's fine if your list the three divisors and the number between 123456789 and 223456789 more than one but not many.
Title: Re: February Number Challenge
Post by: _vince on February 11, 2022, 04:39:03 pm
Is that not a JustBasic user?  What is the difference between JB and LB -- where is the line drawn between liberty and justice?  Which one would you recommend to a beginner?  In an ideal world, would you prefer that everyone here used JB instead of QB64 instead, the same as I would but for FB?
Title: Re: February Number Challenge
Post by: SMcNeill on February 11, 2022, 05:00:36 pm
I'm not really certain what I'm shooting for here, but here's my little go at hunting down divisors:

Code: QB64: [Select]
  1. Screen _NewImage(1280, 720, 32)
  2.  
  3. Dim Shared Primes(1500000) As Long, count As Long
  4. DefLng A-Z
  5. Dim Shared Factors(10000000) As Long
  6. Primes(0) = 2
  7. Print "One moment.... finding primes"
  8. For i = 3 To 1000000 Step 2
  9.     FindPrime (i)
  11. Print "There are "; count; " numbers which are prime that can go into our numbers as factors"
  12.  
  13.  
  14. For i = 123456789 To 123456819
  15.     FindFactor (i)
  17.  
  19. Print "FINISHED"
  20.  
  21.  
  22.  
  23. Sub FindFactor (num)
  24.     Print num; "=";
  25.     Do
  26.         For i = 0 To count
  27.             p = Primes(i)
  28.             If p >= Sqr(num) Then Exit Do
  29.             If num Mod p = 0 Then 'it divides
  30.                 Print p; "x";
  31.                 num = num / p
  32.                 Exit For
  33.             End If
  34.         Next
  35.     Loop Until num = 1
  36.     Print num
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47. Sub FindPrime (num)
  48.     For i = 0 To count
  49.         If num Mod Primes(i) = 0 Then Exit Sub
  50.     Next
  51.     count = count + 1
  52.     Primes(count) = num
  54.  

This takes about 30 seconds or so to generate me a nice large list of prime numbers which I can use to look for factors, and then it happily factors our numbers for us.

Is the goal now to just look for numbers with 3 factors, store those, and then sort them?  What exactly am I supposed to do with this data set now that I've got it?  It's not exactly the clearest of instructions, I don't think.  LOL!

Maybe I just need more coffee??
Title: Re: February Number Challenge
Post by: bplus on February 11, 2022, 05:15:42 pm
Quote
I'm not really certain what I'm shooting for here

List all the numbers between 123456789 and 223456789 that have precisely 3 and only 3 divisors that are non trivial ie not 1 or the number itself. Actually listing the 3 divisors for human check with each number would be good too.

Usually if a number has more than 2 divisors it has a whole slew, only rarely 3.
Title: Re: February Number Challenge
Post by: bplus on February 11, 2022, 05:30:05 pm
Quote from: _vince on February 11, 2022, 04:39:03 pm
Is that not a JustBasic user?  What is the difference between JB and LB -- where is the line drawn between liberty and justice?  Which one would you recommend to a beginner?  In an ideal world, would you prefer that everyone here used JB instead of QB64 instead, the same as I would but for FB?

You keep asking me about JB??? My main attraction is the quality coders they have to teach and help newbies, they come up with interesting ideas to try (such as this little quiz).

Just Basic is the free: student / sampler version of Liberty Basic. I think if you buy Liberty Basic you get lifetime updates of code and all the advanced bells and whistles it has over that student version of Just Basic such as API stuff.

For beginners I recommend QB64 because you can do color with text and it is closer to my idea of Basic programming for the masses and it has a Classic time tested and well developed IDE and Help system. There is a bit more of a learning curve for JB and LB graphics screens but then you can get multiple screens and GUI (not as integrated as VB but well documented and time tested).
Title: Re: February Number Challenge
Post by: bplus on February 11, 2022, 08:05:29 pm
@SMcNeill

I too was confused about primes, we are always talking about prime factors and factoring numbers with primes.

Just concentrate on and count any number that divides evenly into the number we are checking.
2 would be smallest potential divisor and n/2 would be the largest potential divisor.

For any number n you have n/2 - 1 candidates for checking, a little math or other discoveries could (and did  for me) speed up the processing tremendously! If you know a number is prime you know it won't have any divisors, but does that help much? Eh, maybe... ;-))
Title: Re: February Number Challenge
Post by: SMcNeill on February 11, 2022, 11:58:06 pm
Quote from: bplus on February 11, 2022, 08:05:29 pm
@SMcNeill

I too was confused about primes, we are always talking about prime factors and factoring numbers with primes.

Just concentrate on and count any number that divides evenly into the number we are checking.
2 would be smallest potential divisor and n/2 would be the largest potential divisor.

For any number n you have n/2 - 1 candidates for checking, a little math or other discoveries could (and did  for me) speed up the processing tremendously! If you know a number is prime you know it won't have any divisors, but does that help much? Eh, maybe... ;-))

Actually, wouldn't n/8 would be the largest number to check as you're looking for 3 factors, and they have to be 2 x 2 x 2 at a minimum. 


My idea is to pre-generate the prime numbers (which would be the factors), and then we'd only have to check primes from 2 to SQR(n) to check for factors for our number, with it growing ever smaller with each factor we pull out of it.  My example does this nicely and fairly quickly.  All I need to add, apparently, is a counter for number of factors found and if only 3 exist then I have a valid number.

I was just curious about the rest of the problem -- store the largest factor and sort the results.  Are we sorting via that stored, largest factor?  By the number itself? 

I'm also curious about what the question calls a non-trivial divisor. 

Let's use 16 as an example:

The factors are 2 x 2 x 2 x 2...

But could we say it has 3 nontrivial divisors?  2 x 2 x 4?

4 is still a divisor of 16, even if it isn't the most simplified or lowest common denominator...

If 2 x 2 x 4 counts, then the program becomes much quicker and simpler to run.  Count factors, find 3, stop at the 3rd one and store it as it's going to be the highest factor.  Then just sort your stored array.


Heck, if 2 x 2 x 4 counts for 16, then I'd just assemble a small preset array for quick elimination of most numbers.

For example, any number ending in zero can be instantly solved -- 2 * 5 * n /10 would give you the greatest denominator with 3 factors.

Check for numbers evenly divisible by 4, 6, 9, 10, 14...  (2 * 2) (2 * 3) (3 * 3) (2 * 5) (2 * 7)..  A quick list of a dozen fast pre-checks, or so, could probably eliminate over half of the problem with a single pass.  The rest you can just factor out like normal afterwards.  <-- It'd cut down on solving time considerably.
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 09:29:22 am
Quote
Just concentrate on and count any number (>1 and <N) that divides evenly into the number we are checking.
2 would be smallest potential divisor and n/2 would be the largest potential divisor.

Here is a ListNonTrivialDivisors$ function to show the divisors of a number and the count of them:
Code: QB64: [Select]
  1. DefLng A-Z
  2.  
  3. For i = 200 To 220   'test numbers from 200 to 220
  4.     Print i, ListNonTrivialDivisors$(i)
  6.  
  7. Function ListNonTrivialDivisors$ (n)
  8.     If n > 1 Then
  9.         For i = 2 To n \ 2
  10.             If n Mod i = 0 Then
  11.                 count = count + 1
  12.                 If rtn$ <> "" Then rtn$ = rtn$ + ", " + _Trim$(Str$(i)) Else rtn$ = _Trim$(Str$(i))
  13.             End If
  14.         Next
  15.         If rtn$ = "" Then rtn$ = _Trim$(Str$(n)) + " is a prime number." Else rtn$ = rtn$ + " Count:" + Str$(count)
  16.         ListNonTrivialDivisors$ = rtn$
  17.     End If
  19.  

  [ This attachment cannot be displayed inline in 'Print Page' view ]  
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 09:57:12 am
To give away the farm: there is only one kind of number that has exactly 3 divisors and you might use code similar to what I have above to search for them if you find the first 3 you should see the light :)
Title: Re: February Number Challenge
Post by: SMcNeill on February 12, 2022, 10:31:41 am
Quote from: bplus on February 12, 2022, 09:57:12 am
To give away the farm: there is only one kind of number that has exactly 3 divisors and you might use code similar to what I have above to search for them if you find the first 3 you should see the light :)

I would think, without testing, the solution would have to be prime * prime * prime ^ 2.

Examples:

16 = 2 * 2 * 4 (factors = 2, 4, 8, not counting 1 and 16)
81 = 3 * 3 * 9 (factors = 3, 9, 27, not counting 1 and 81)

The solution would be n ^ 4 > 123456789 and <223456789.

The pattern seems to fit, as long as I'm not missing something.
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 10:59:38 am
The light is dawning :)

Now see the awesome mass of integers whose 4th power are between 123456789 and 223456789 ha, ha!

Then finally find the ones that are primes ^ 4, in the blink of the eye!
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 11:18:42 am
@SMcNeill you are using strange way of listing 3 divisor's as a single multiple of prime factors 16 = 2*2*4

For clarity:
The divisors of 16 are 2, 4, and 8 right? Those are the only numbers that divide 16 other than 1 and 16.
The divisors of 81 are 3, 9 and 27...

So the pattern is...




Title: Re: February Number Challenge
Post by: SMcNeill on February 12, 2022, 11:32:34 am
Quote from: bplus on February 12, 2022, 10:59:38 am
The light is dawning :)

Now see the awesome mass of integers whose 4th power are between 123456789 and 223456789 ha, ha!

Then finally find the ones that are primes ^ 4, in the blink of the eye!

Aye.  I was working on the wrong problem.  My thinking was we had to break it down to the base factors, check for only 3, and then seek the highest denominator, save, and sort.

Example: 30 = 2 * 3 * 5  (of course there's 6 and 15, but they're still composite factors so I didn't count them).

So I was working to find values with 3 primes between 123456789 and 223456789 -- which is quite a bit different than what was actually intended!

I told ya I needed a lot more coffee to understand the problem!  As a programmer, the hardest code to write is for a problem you don't comprehend.  The example screenshot of what was actually expected DINGED the solution almost instantly for me.  ;)
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 11:54:24 am
Quote
As a programmer, the hardest code to write is for a problem you don't comprehend.

LOL It's the hardest to get right! no so hard to come up with garbage ;-))
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 11:56:10 am
You've probably done right if you get 3 integers between 123456789 and 223456789 with only 3 divisors.

Or I've got the whole thing wrong too! LOL
Title: Re: February Number Challenge
Post by: SMcNeill on February 12, 2022, 12:26:05 pm
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...
Title: Re: February Number Challenge
Post by: SMcNeill on February 12, 2022, 12:36:05 pm
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

(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.)
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 01:13:15 pm
Yes, those answers match the ones I got.

Here is how I worked it out:

Quote
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
  16. Locate row + 1, 1
  17. Print "End of run."
  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

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
  16. Locate row + 1, 1
  17. Print "End of run."
  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
  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
  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
  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
  10. 'verify my choice of n stop
  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.  
Title: Re: February Number Challenge
Post by: SMcNeill on February 12, 2022, 01:42:07 pm
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.

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.
Title: Re: February Number Challenge
Post by: bplus on February 12, 2022, 01:54:04 pm
Quote
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.)


Title: Re: February Number Challenge
Post by: _vince on February 19, 2022, 02:54:23 pm
Quote from: bplus on February 11, 2022, 02:14:18 pm
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?
Title: Re: February Number Challenge
Post by: bplus on February 19, 2022, 03:23:34 pm
see Discord PM
Title: Re: February Number Challenge
Post by: SMcNeill on February 19, 2022, 03:40:27 pm
Quote from: _vince on February 19, 2022, 02:54:23 pm
Who is the best programmer there? tsh, Rod, or technotitlick?

ME, of course!   😂😂
Title: Re: February Number Challenge
Post by: _vince on February 19, 2022, 04:01:14 pm
wow Steve, you also program in Liberty BASIC?
Title: Re: February Number Challenge
Post by: SMcNeill on February 19, 2022, 05:09:55 pm
Quote from: _vince on February 19, 2022, 04:01:14 pm
wow Steve, you also program in Liberty BASIC?

Nope.  Never heard of it.  I'm just >THAT< good!  😁
Text Only | Text with Attachments