Resolved Help with a logical programming task

[rammfire]

Hi. I need your help with a small logic problem. The essence of the task:


There are numbers from 1 to N, N = 50, you need to divide the numbers into several groups
so if one number is divided by another, then these numbers fall into different groups.
The result of this partition is M groups, for N = 50, M = 6.

Example:

N = 50
The groups turned out like this:

Group 1: 1
Group 2: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Group 3: 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49
Group 4: 8 12 18 20 27 28 30 42 44 45 50
Group 5: 16 24 36 40
Group 6: 32 48
M = 6
===========

N = 10
The groups turned out like this:

Group 1: 1
Group 2: 2 7 9
Group 3: 3 4 10
Group 4: 5 6 8

I was able to solve this problem using an array of arrays, where I wrote intermediate data and did a bunch of different array operations. Unfortunately, my algorithm when working with, for example, a billion numbers required up to 8 GB of RAM and could count up to 14 hours on a single processor. Adding the rest of the cores to the work of course reduced this time, but the problem of RAM consumption has not gone away.


I was able to make a faster algorithm, but I can't bring it to mind. Maybe someone here can help me?

            int magicNumber = 50;

            int groups = (int)(Math.Log(magicNumber, 2) + 1);

            using (StreamWriter streamWriter = new StreamWriter("output.result"))
            {
                for (int i = 1; i < groups; i++)
                {
                    if (i == 1)
                    {
                        streamWriter.Write("1");
                    }
                    for (int j = i + 1; j < magicNumber; j++)
                    {
                        if (j % i == 0)
                        {
                            
                        }

                        else

                        {
                            streamWriter.Write(j + " ");
                        }
                    }
                    streamWriter.WriteLine();
                }
                Write("\n");
}

Result is:

1
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49
5 6 7 9 10 11 13 14 15 17 18 19 21 22 23 25 26 27 29 30 31 33 34 35 37 38 39 41 42 43 45 46 47 49
6 7 8 9 11 12 13 14 16 17 18 19 21 22 23 24 26 27 28 29 31 32 33 34 36 37 38 39 41 42 43 44 46 47 48 49

Expected result in the example.


Thank you in advance.

 

[Skydiver]

you need to divide the numbers into several groups
so if one number is divided by another, then these numbers fall into different groups.

What is the exact rule for why a number would fall into a particular group?

For example, all the prime numbers 2, 3, 5, 7, 11, 13, ... are not divisible by any other number, but somehow they are in the groups.

 

[Skydiver]

Ah, I think I see... you want each of the group members to be relatively prime to each other. But with N = 10, this seems to be a valid grouping:

Group 1: 1
Group 2: 2 3 5 7
Group 3: 4 6 9 10
Group 4: 8

 

[rammfire]

Ah, I think I see... you want each of the group members to be relatively prime to each other. But with N = 10, this seems to be a valid grouping:

Group 1: 1
Group 2: 2 3 5 7
Group 3: 4 6 9 10
Group 4: 8

If the current number is 2 times larger than the first number in the group, it is, and everything that follows it is guaranteed to go to the next group.
I was almost able to develop the correct algorithm, but it still produces repeating numbers:

 for (int i = 2; i <= 6; i++)
            {
                for (int j = 2; j <= 50; j++)
                {
                    result = j % i;
                    if (result == 0)
                    {
                        Write("");
                    }
                    
                    else if (result == 1)
                    {
                        Write(j + " ");
                    }
                }
                Write("\n");
            }
                ReadLine();

Result is:

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49
5 9 13 17 21 25 29 33 37 41 45 49
6 11 16 21 26 31 36 41 46
7 13 19 25 31 37 43 49

 

[rammfire]

I have a more sophisticated algorithm for solving this problem that produces guaranteed correct numbers, but the problem is that it consumes too much RAM. For example, if you put 1 billion numbers in my current algorithm, you will need up to 10 GB of RAM and almost a day on a single core to output the result.

 

[Skydiver]

Outline your "more sophisticated algorithm" instead of just alluding to it.

I've got a more brute force O(n^2) time complexity algorithm that only requires O( n ) space:

MakeRelativePrimeGroups: N : int
groups = new List<List<int>>();
for each number 1 to N do
    added = false

    for each group in groups
        if IsRelativelyPrime(number, group)
            group.Add(number)
            added = true
            break

    if not added
        groups.Add(new List<int>({ number }))

return groups



IsRelativelyPrime: number : int, group : List<int>
    => group.All(i => number % i != 0)

 

[Skydiver]

Out of curiosity, I ran N = 1000000. It took about 17 minutes on my laptop running on battery using that brute force algorithm I outlined above. I bet a more efficient algorithm would be even faster. 4 bytes per int should take up about 4MB of RAM.

 

[Skydiver]

Forgive my use of the term "relatively prime" in post #3 and #6. There is a specific mathematical definition for that term which requires that they do not share any common factors. 14 and 21 are not relatively prime, but they both belong in group 2 as shown in the OP.

 

[rammfire]

In general, I solved this problem a little differently. But it works much faster

result | C# Online Compiler | .NET Fiddle

result | Test your C# code online with .NET Fiddle code editor.

dotnetfiddle.net

 

[Skydiver]

Yes, grouping by the powers of 2 makes a nice O( n ) time and space solution!

 

[Skydiver]

And here's my solution by adapting the linear Sieve of Eratosthenes to help find the prime numbers for group 2, and figure out which groups the other composite numbers will go into. This produces groups that look like the original posted question.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    struct SieveEntry
    {
        public int LowestPrime { get; private set; }
        public int FactorCount { get; private set; }

        public bool IsPrime => LowestPrime == 0;

        public void MarkAsPrime(int i)
            => SetValues(i, 1);

        public void SetValues(int lowestPrime, int factorCount)
        {
            LowestPrime = lowestPrime;
            FactorCount = factorCount;
        }
    }

    IEnumerable<IEnumerable<int>> ComputeGroups(int max)
    {
        var sieve = new SieveEntry[max + 1];
        var groups = new List<List<int>>();

        groups.Add(new List<int>(new[] { 1 }));

        var primes = new List<int>();
        groups.Add(primes);

        for(int i = 2; i <= max; i++)
        {
            if (sieve[i].IsPrime)
                sieve[i].MarkAsPrime(i);

            AddToGroupWithSameNumberOfFactors(i);
            MarkDownstreamComposites(i);
        }

        return groups;

        void AddToGroupWithSameNumberOfFactors(int i)
        {
            int factorCount = sieve[i].FactorCount;
            while (factorCount >= groups.Count())
                groups.Add(new List<int>());

            groups[factorCount].Add(i);
        }

        void MarkDownstreamComposites(int i)
        {
            int factorCount = sieve[i].FactorCount + 1;
            foreach (var prime in primes.Where(p => p <= sieve[i].LowestPrime))
            {
                var index = i * prime;
                if (index > max)
                    break;
                sieve[index].SetValues(prime, factorCount);
            }
        }
    }

    void ShowResults(IEnumerable<IEnumerable<int>> groups)
    {
        int i = 1;
        foreach (var group in groups)
            Console.WriteLine("Group {0}: {1}", i++, string.Join(" ", group));
    }

    void Run(int n)
    {
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        var groups = ComputeGroups(n);
        stopwatch.Stop();
        Console.WriteLine($"Number of Groups: {groups.Count()}");
        Console.WriteLine($"Elapsed time: {stopwatch.Elapsed}");
        ShowResults(groups);
    }

    static void Main(string [] args)
    {
        int n = 50;
        if (args?.Length == 1)
            int.TryParse(args[0], out n);
        new Program().Run(n);
    }
}

This code also runs in O( n ) time and space. Technically the space is O( 3 * n ), but since constants are removed in complexity analysis, it's still considered as O( n ).

I noticed that each of the group members shared a common characteristic: they all had the same number of prime factors in them. Group 1 which contains only 1, had no prime factor. All the prime numbers in group 2 have just 1 prime factor (since they are prime). All in group 3 had 2 prime factors each. All in group 4 had 3 prime factors. Etc.

On the same laptop, N = 1000000 ran in 54 seconds.