February Number Challenge

[bplus]

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

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.

[_vince]

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?

[SMcNeill]

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)
10. Next
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)
16. Next
17.  
18. Print
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
37. End Sub
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
53. End Sub
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??

[bplus]

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.

[bplus]

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).

[bplus]

@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... ;-))

[SMcNeill]

@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.

[bplus]

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)
5. Next
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
18. End Function
19.  

  [ You are not allowed to view this attachment ]  

[bplus]

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 :)

[SMcNeill]

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.

[bplus]

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!

[bplus]

@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...

[SMcNeill]

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.  ;)

[bplus]

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 ;-))

[bplus]

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