Integer Partitions

[dutch]

This is an interesting Mathologer video:
| The hardest "What comes next?" (Euler's pentagonal formula)
| https://www.youtube.com/watch?v=iJ8pnCO0nTY

It's about the number of ways to partition integers:

0: 1 (0)
1: 1 (1)
2: 2 (1+1, 2)
3: 3 (1+1+1, 1+2, 3)
4: 5 (1+1+1+1, 1+1+2, 2+2, 1+3, 4)
5: 7 (1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 2+3, 1+4, 5)

The fibonacci-like pattern he arrives at by about 12:00 is interesting.
It has a programming challenge at about 16:04.

Here's more of the sequence of integer partitions:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, ...

[dutch]

BTW, the answer to the programming challenge is

11,956,824,258,286,445,517,629,485 ways to partition the number 666.

You need to use __int128. cout won't print it, so you can use something like:

void print(__int128 n) {
    if (n < 1000)
        std::cout << int(n);
    else {
        print(n / 1000);
        std::cout << ',' << std::setfill('0') << std::setw(3) << int(n % 1000) << std::setfill(' ');
    }
}

[lastchance]

For the recursion, see
https://en.wikipedia.org/wiki/Partition_(number_theory)

#include <iostream>
#include <vector>
using namespace std;


class BigInt
{
public:
   vector<int> digits;       // note: digits stored in REVERSE order;
   BigInt( int n = 0 );      // construct from integer; default is 0
};

//------------------

BigInt::BigInt( int n )   
{
   digits.clear();
   if ( n == 0 )
   {
      digits.push_back( 0 );
   }
   else
   {
      while ( n )
      {
         digits.push_back( n % 10 );
         n /= 10;
      }
   }
}

//------------------

BigInt operator + ( const BigInt &a, const BigInt &b )
{
   BigInt result = a;
   int bsize = b.digits.size();

   for ( int i = 0, carry = 0; i < bsize || carry > 0; i++ )
   {
      if ( i < result.digits.size() ) carry += result.digits[i];
      if ( i < b.digits.size()      ) carry += b.digits[i];
      int digit = carry % 10;
      carry /= 10;
      if ( i < result.digits.size() ) result.digits[i] = digit;
      else                            result.digits.push_back( digit );
   }
   return result;
}

//------------------

ostream &operator << ( ostream &strm, const BigInt &a )
{
   for ( int i = a.digits.size() - 1; i >= 0; i-- ) strm << a.digits[i];
   return strm;
}

//======================================================================

int main()
{
   int N = 666;
   vector< vector<BigInt> > pk(N+1,vector<BigInt>(N+1));
   vector<BigInt> p(N+1);
   pk[0][0] = p[0] = 1;
   for ( int n = 1; n <= N; n++ )
   {
      for ( int k = 1; k <= n; k++ ) 
      {
         pk[n][k] = pk[n-k][k] + pk[n-1][k-1];        // KEY RECURSION
         p[n] = p[n] + pk[n][k];
      }
      cout << n << ": " << p[n] << '\n';
   }
}

1: 1
2: 2
3: 3
4: 5
5: 7
6: 11
7: 15
8: 22
9: 30
10: 42
11: 56
12: 77

--- Lots of lines ---

660: 8947840456000332817673697
661: 9391599660555044587641517
662: 9857016966290401433259592
663: 10345132652677367520056676
664: 10857036174895938656583295
665: 11393868451739000294452939
666: 11956824258286445517629485

[dutch]

The dynamic programming solution is interesting (and +1 for using a BigInt), but the method in the video is more efficient in both space and time. The following also uses unsigned __int128 which limits it's highest input to 1458.

#include <iostream>
#include <iomanip>
#include <vector>

using uint128 = unsigned __int128;
const int HighestAnswerable = 1458;
// Highest answer:  336988065393447621514574974879775699372
// Highest uint128: 340282366920938463463374607431768211455

void print(uint128 n) {
    using namespace std;
    if (n < 1000)
        cout << int(n);
    else {
        print(n / 1000);
        cout << setfill('0') << setw(3) << int(n % 1000) << setfill(' ');
    }
}

int main() {
    const int Size = 666;
    if (Size > HighestAnswerable) { std::cout << "overflow\n"; return 1; }

    std::vector<uint128> vals{1};
    for (int n = 0; n < Size; ++n) {
        //std::cout << std::setw(4) << n << ": ";
        //print(vals.back()); std::cout << '\n';
        uint128 sum = 0;
        int pos = 1;
        for (int i = 0; pos <= int(vals.size()); ++i) {
            uint128 v = vals[vals.size() - pos];
            if (i % 4 < 2) sum += v; else sum -= v;
            pos += (i % 2 ? i + 2 : (i + 2) / 2);
        }
        vals.push_back(sum);
    }
    std::cout << std::setw(4) << Size << ": ";
    print(vals.back()); std::cout << '\n';
}

[lastchance]

Yes, I rather short-cut the solution: I already had a BigInt class to hand and the recursive solution was quick to code but not very efficient.

After the number-of-the-beast challenge his next chapter was on a route to finding primes that I've never seen before. I need to digest that from the video and see how it matches up to a sieve or similar methods.

[dutch]

Here's a version of the method in the video using (modified) BigInt.

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

using uint = unsigned;
using ulong = unsigned long; // assuming 64-bit

const ulong Chunk = 1000000000000000000;
const uint ChunkSize = 18; // number of zeroes in Chunk

class BigInt {
    vector<ulong> chunks;
public:
    BigInt(ulong n = 0);
    BigInt& operator+=(const BigInt& rhs);
    BigInt& operator-=(const BigInt& rhs);
    friend ostream& operator<<(ostream& out, const BigInt& b);
};

BigInt:: BigInt(ulong n) {
    do chunks.push_back(n % Chunk); while (n /= Chunk);
}

BigInt& BigInt::operator+=(const BigInt& rhs) {
    ulong carry = 0;
    for (uint i = 0; i < rhs.chunks.size() || carry > 0; ++i) {
        if (i < chunks.size())     carry += chunks[i];
        if (i < rhs.chunks.size()) carry += rhs.chunks[i];
        ulong newchunk = carry % Chunk;
        carry /= Chunk;
        if (i < chunks.size()) chunks[i] = newchunk;
        else                   chunks.push_back(newchunk);
    }
    return *this;
}

// Assumes *this is larger than rhs.
BigInt& BigInt::operator-=(const BigInt& rhs) {
    for (uint i = 0; i < rhs.chunks.size(); ++i) {
        if (chunks[i] < rhs.chunks[i]) { // need to borrow
            uint j = i + 1;
            for ( ; chunks[j] == 0; ++j) ;
            do {
                --chunks[j];
                chunks[j - 1] += Chunk;
            } while (--j > i);
        }
        chunks[i] -= rhs.chunks[i];
    }
    while (chunks.size() > 1 && chunks.back() == 0)
        chunks.resize(chunks.size() - 1);
    return *this;
}

// Assumes b is not empty.
ostream& operator<<(ostream& out, const BigInt& b) {
    uint i = b.chunks.size();
    out << b.chunks[--i] << setfill('0');
    while (i--) out << setw(ChunkSize) << b.chunks[i];
    return out << setfill(' ');
}

int main() {
    const uint Size = 10000;
    vector<BigInt> vals{1};
    for (uint n = 0; n < Size; ++n) {
        //cout << setw(6) << n << ": " << vals.back() << '\n';
        BigInt sum;
        uint pos = 1;
        for (uint i = 0; pos <= uint(vals.size()); ++i) {
            BigInt v = vals[vals.size() - pos];
            if (i % 4 < 2) sum += v; else sum -= v;
            pos += (i % 2 ? i + 2 : (i + 2) / 2);
        }
        vals.push_back(sum);
    }
    cout << setw(6) << Size << ": " << vals.back() << '\n';
}

[againtry]

After the number-of-the-beast challenge his next chapter was on a route to finding primes that I've never seen before. I need to digest that from the video and see how it matches up to a sieve or similar methods.

On face value this aspect is interesting but on closer examination and using the Sieve of Eratosthenes it's trivial by a simple adjustment to the Sieve algorithm using the fact that the Sieve 'automatically' calculates all the factors of a particular number. Maybe the trivialty is the interesting thing.

#include <iostream>

int main()
{
    const int sz{100000};
    
    int sieve[sz];
    for(int i = 0; i < sz; i++)
    {
        sieve[i] = 0;
    }
    
    
    for ( int i = 1; i <= sz; i++)
    {
        for (int j = i; j < sz; j += i)
        {
            sieve[j] += i;
        }
    }
    
    
    sieve[1] = 2;
    for(int i = 1; i < sz; i++)
    {
        if(sieve[i] - i - 1  == 0)
            std::cout << i << ' ';
    }
    
    std::cout << '\n';
    
    return 0;
}

.

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101

...

99859 99871 99877 99881 99901 99907 99923 99929 99961 99971 99989 99991 
Program ended with exit code: 0

[seeplus]

1 is not considered a prime number. There is no need to explicitly set sieve[1] to 2.

#include <iostream>

int main()
{
	const int sz {100};

	int sieve[sz] {0};

	for (int i = 1; i <= sz; ++i)
		for (int j = i; j < sz; j += i)
			sieve[j] += i;

	for (int i = 2; i < sz; ++i)
		if (sieve[i] - i - 1 == 0)
			std::cout << i << ' ';

	std::cout << '\n';
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

[againtry]

Come in spinner - bait, hook line and sinker taken in one gulp. I didn't say it was.