Finding number that 1-20 will divide evenly into

[adam2016]

what sounds like a simple problem is giving me just that... problems

within a couple of second I came up with the algorithm to get 2520(1-10) but when I try to find the first 20 it doesn't seem to find it. I'm even using an unsigned long long to hold i!

unsigned long divsion()
{

    for(unsigned long long i = 1; i < 300000; i++)
    {
        for(int j = 1; j <= 20; ++j){

            if(i % j == 0){

                if(j == 20)
                    return i;
                }
            else
                break;
        }
    }
    return 1;
}

[dutch]

The answer is 232792560, so you're not looking far enough.
Remember that these kinds of problems are looking for a "clever" solution that you actually need to think about before coding, not a brute force search. Although a brute force search can work in this case, what if the limit was 40 instead of 20? It could take quite a while.

#include <iostream>
#include <iomanip>

using UL = unsigned long;

bool isprime(UL n)
{
    if (n <= 2) return n == 2;
    if (n % 2 == 0) return false;
    for (UL d = 3; d * d <= n; d += 2)
        if (n % d == 0)
            return false;
    return true;
}

// Only works up to 47 for 64-bit long
UL divisible_up_to(UL limit)
{
    UL n = 1;
    for (UL p = 2; p <= limit; ++p)
        if (isprime(p))
        {
            UL f = 1;
            while (f * p <= limit) f *= p;
            n *= f;
        }
    return n;
}

int main()
{
    for (UL n = 2; n <= 47; ++n)
        std::cout << std::setw( 2)  << n
                  << std::setw(21) << divisible_up_to(n) << '\n';
}

 2                    2
 3                    6
 4                   12
 5                   60
 6                   60
 7                  420
 8                  840
 9                 2520
10                 2520
11                27720
12                27720
13               360360
14               360360
15               360360
16               720720
17             12252240
18             12252240
19            232792560
20            232792560
21            232792560
22            232792560
23           5354228880
24           5354228880
25          26771144400
26          26771144400
27          80313433200
28          80313433200
29        2329089562800
30        2329089562800
31       72201776446800
32      144403552893600
33      144403552893600
34      144403552893600
35      144403552893600
36      144403552893600
37     5342931457063200
38     5342931457063200
39     5342931457063200
40     5342931457063200
41   219060189739591200
42   219060189739591200
43  9419588158802421600
44  9419588158802421600
45  9419588158802421600
46  9419588158802421600
47 18445529768394128032

This table can be generated in a millisecond.
Your brute force method would literally take years.
That's the power of analyzing (thinking about the structure of) the problem and writing an algorithm that takes advantage of its structure.

[lastchance]

#include <iostream>
using namespace std;

using INT = unsigned long long;

INT HCF( INT a, INT b ) { return b ? HCF( b, a % b ): a; }

int main()
{
   for ( INT p = 1, n = 2; n <= 47; n++ )
   {
      p = ( p / HCF( p, n ) ) * n;
      cout << n << "  " << p << '\n';
   }
}

[adam2016]

@Dutch

how come a brute force method won't work at least in my case?

and it would take years if I was to search for a number such that numbers 1-40 divide evenly into?

*edit I modified my code a little to put i as the largest number an unsigned long long could hold

it worked and I got - 232792560 but as you mentioned it was extremely slow taking almost 10 seconds! but certainly not years. - https://ibb.co/V2Gj06R

but as you mentioned if you changed 20 to 40, it would take years, how did you come up with that approximation, big O notation? I changed the 20 to 40, and ran the program, and already it's been running for 10 minutes and has no sign of stopping anytime soon.

also lastly, how come doing a test for if a number is prime greatly reduces the execution time?

I'm trying to figure out the algorithm you used and by tracing through the loop(s) this is what I get for limit = 4.

P = 2 n = 1
   
   f = 1
   f*p = 2 -> f*p <= 4
     f = 2
     n = 2

    f*p = 4 -> f*p <= 4
      f = 4
      n = 4

p = 3 n = 4

   f = 1
   f*p = 3 -> 3 <= 4
     f = 3
     n = 12

     return 12

How come we use multiplication as a test case instead of the mod operator? and is there a name for this particular algorithm?

  unsigned long sumMultiples()
{

    for(unsigned long long i = 1; i < 4294967295; i++)
    {
        for(int j = 1; j <= 20; ++j){

            if(i % j == 0){

                if(j == 20)
                    return i;
                }
            else
                break;
        }
    }
    return 1;
}

[dutch]

how come a brute force method won't work at least in my case?

I said it would work in your case, but that's only because it's a small case like 20 as opposed to a large case like 40. But those kinds of questions are not looking for mindless brute force solutions. What's the use of that? What could you possibly learn? It's not like the answer itself is important.

I modified my code a little to put i as the largest number an unsigned long long could hold

No you didn't. The largest number an unsigned long long can hold is 2^64 - 1, which is 18446744073709551615. (Using ^ to mean exponentiation instead of it's usual meaning in C++.)

how did you come up with that approximation [of it taking years]

As you say, it's just an approximation. 2^64 is about 18^18 (18 quintillion). Suppose you had an algorithm/computer that could search a billion (1^9) values per second. 18^18 / 1^9 = 18^9, or 18 billion seconds, which is over 500 years. Even if you could search a trillion a second it would take over 6 months.

how come doing a test for if a number is prime greatly reduces the execution time?

Because if you THINK about the problem you will see that the answer is obviously made up of the largest number of factors of the primes that occur in all the values up to the limit (20 in your case). I initially just came up with the answer without a program. The largest number of 2's occurs in 16, which is 2^4, so obviously the answer must have 4 2's in it as factors. The largest number of 3's is in 9, which is 2^3. None of the other prime factors can occur more than once since the next prime is 5 and 5^2 is 25, which is already over 20. So the answer is:
2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560.

For 40, we have:
2^5 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37
= 5342931457063200

is there a name for this particular algorithm?

No. I just made it up. However, it's far from optimal. Kind of crap, really.

[adam2016]

I think I'm on the cusp of this one, hang with me :)

Let's say our limit is 8 instead of 20 to make things simple

so we want a number that will divide evenly by (1-8)

8's factors: 2 * 2 * 2
7's factors: 7
6's factors: 3 * 2
5's factors: 5
4's factors: 2 * 2
3's factors: 3
2's factors: 2
1's factors: 1

*by factors I mean prime factors

let's multiply all these factors together

(2^3) * (7) * (3 * 2) * (5) * (2^2) * (3) * (2) * (1) = 40320

but I noticed when I only include 2^3 and drop the other 2's I get

(2^3) * (7) * (3) * (5) * (1) = 840


and 840 is indeed the correct answer why did we discard the other 2's? I do vaguely remember from somewhere, that we only include the largest amount of primes from a number such as 2^3 in the above example and we ignore the rest. Is this true and how come the other 2's and 3 are dropped?

the problem you will see that the answer is obviously made up of the largest number of factors of the primes that occur in all the values up to the limit

[dutch]

You only need it to be divisible by 1 to 8.
If it had 4 factors of 2 it would be divisible by 16.
If it had 2 factors of 3 it would be divisible by 9.
You only need the max number of times the factor appears in any requested divisor.
So what is the smallest number divisible by all these divisors: 4, 9, 24, 30 ?

BTW, I should add that my answer for 47 is wrong. It actually is 442720643463713815200, which overflows a 64-bit value.

[adam2016]

If it had 4 factors of 2 it would be divisible by 16.
If it had 2 factors of 3 it would be divisible by 9.
You only need the max number of times the factor appears in any requested divisor.

not exactly sure still, could you give an example. I'm probably over complicating

especially this

You only need the max number of times the factor appears in any requested divisor.

I think this is where I'm going wrong

So what is the smallest number divisible by all these divisors: 4, 9, 24, 30 ?

very good question, I guess I'll break it down by all of it's prime factors

4 = 2*2
9 = 3*3
24 = 2^3 * 3
30 = 5 * 3 * 2


sorry I originally said 120* it should be 2^3 * 3^2 * 5 = 360 I think

I know that way works, but not sure why it works still, specifically not sure we discard the max number of times a factor appears in each number

[dutch]

You got the right answer.

specifically not sure we discard the max number of times a factor appears in each number

I have no idea what you mean by that. It sounds the opposite of what I said. Maybe English isn't your first language. Anyway, I'm getting tired of this. I'm done man.

[adam2016]

Okay...........Thanks, I guess??