Resolved Help with a logical programming task

rammfire

Member
Joined
Sep 1, 2020
Messages
6
Programming Experience
Beginner
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:

C#:
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?

C#:
            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:

C#:
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

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
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

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
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:
C#:
Group 1: 1
Group 2: 2 3 5 7
Group 3: 4 6 9 10
Group 4: 8
 

rammfire

Member
Joined
Sep 1, 2020
Messages
6
Programming Experience
Beginner
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:
C#:
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:
C#:
 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:
C#:
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

Member
Joined
Sep 1, 2020
Messages
6
Programming Experience
Beginner
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

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
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:
C#:
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

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
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.
 
Last edited:

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
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.
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
Yes, grouping by the powers of 2 makes a nice O( n ) time and space solution!
 

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
3,166
Location
Chesapeake, VA
Programming Experience
10+
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.

C#:
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.
 
Top Bottom