Can you detect any formula here?

[SlurrerOfSpeech]

I'm trying to figure out a basic formula from the below

1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 3
6 -> 4
7 -> 5
8 -> 7
9 -> 10
10 -> 14
11 -> 19
12 -> 26
13 -> 36
14 -> 50
15 -> 69
16 -> 86
17 -> 117
18 -> 167
19 -> 180
20 -> 238
21 -> 352
22 -> 319
23 -> 374
24 -> 625
25 -> 480
26 -> 505
27 -> 875
28 -> 603
29 -> 501
30 -> 965
31 -> 658
32 -> 378
33 -> 808
34 -> 581
35 -> 2386
36 -> 580

If you're curious where I'm getting these results from, it's a brute force algorithm I wrote that gets the number of configurations of blocks of size 1x4 and 4x1 blocks that can cover a 4xN board. But I'd ideally like to make this an O(1) algorithm if I can figure out what the formula is ...

 

[SlurrerOfSpeech]

Okay, I should probably post the code I wrote that generated that mapping. This is part of a larger problem I'm trying to solve.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq; 

public class Solution
{
    public static int Factorial(int k)
    {
        int p = 1;
        for(; k > 1; --k)
            p *= k;
        return p;
    }
   
    public static int NumberCombinations(int m, int n)
    {
        return Factorial(m + n) / (Factorial(n) * Factorial(m));
    }
   
    static int NumberConfigurations(int n)
    {   
        var range = Enumerable.Range(0, n + 1); // 0, 1, ..., n
        return (from i in range 
               from j in range
                where (i * 4 + j) == n
                select i * j == 0 // either i or j is 0
                      ? 1 
                      : NumberCombinations(i,j)
                ).Sum();
       
    }
   
    public static void Main(String[] args)
    {
        for(int i = 1; i < 50; ++i)
            Console.WriteLine(i.ToString() + " -> " + NumberConfigurations(i).ToString());
    }
}

 

[Ibix]

To cover a 4xN grid with 4x1 tiles takes N tiles, surely? Each one covers a row.

 

[SlurrerOfSpeech]

To cover a 4xN grid with 4x1 tiles takes N tiles, surely? Each one covers a row.

4x1 or 1x4 tiles.

For example, if N=5 you could use 5 4x1 tiles, 1 4x1 tile followed by 4 1x4 tiles stacked, or 4 1x4 tiles stacked followed by one 4x1 tiles.

I see this as equivalent to first solving the equation

4i + j = n

for non-negative integers i,j and then for the pairs where i,j>0 you have (i+j)!/(i! * j!) ways of arranging them.

 

[SlurrerOfSpeech]

4x1 or 1x4 tiles.

For example, if N=5 you could use 5 4x1 tiles, 1 4x1 tile followed by 4 1x4 tiles stacked, or 4 1x4 tiles stacked followed by one 4x1 tiles.

I see this as equivalent to first solving the equation

4i + j = n

for non-negative integers i,j and then for the pairs where i,j>0 you have (i+j)!/(i! * j!) ways of arranging them.

Hmmmm I'm wondering whether my algorithm is even correct. Because this is failing most of the test cases. I may as well admit that what I'm trying to solve is https://www.hackerrank.com/challenges/red-john-is-back

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

public class PrimeNumberChecker
{
    private Dictionary<long,bool> cache = new Dictionary<long,bool>();
   
    public bool IsPrime(long k)
    {
        if(cache.ContainsKey(k))
            return cache[k];
       
        bool isPrime = true; 
        for(long j = 2; j < k; j++)
        {
            if(k % j == 0) 
            {
                isPrime = false;
                break;
            }
        }
        cache[k] = isPrime;
        return isPrime;       
    }
}

public class FormulaMachine
{
    private PrimeNumberChecker pChecker = new PrimeNumberChecker();
   
    public IEnumerable<long> PrimeNums(long num)
    {
        for(long i = 2; i <= num; i++)
            if(pChecker.IsPrime(i))
                yield return i;
    }
   
    private static long Factorial(long k)
    {
        long p = 1;
        for(; k > 1; --k)
            p *= k;
        return p;
    }
   
    private static long NumberCombinations(long m, long n)
    {
        return Factorial(m + n) / (Factorial(n) * Factorial(m));
    }
   
    public long NumberConfigurations(long n)
    {   
        var range = Enumerable.Range(0, (int)(n + 1)); // 0, 1, ..., n
        return (from i in range 
               from j in range
                where (i * 4 + j) == n
                select NumberCombinations(i,j)
                ).Sum();
       
    }
}

public class Solution
{   
    public static void Main(String[] args)
    {
        var machine = new FormulaMachine();
        for(long t = 0, T = long.Parse(Console.ReadLine()); t < T; ++t)
        {
            long N = long.Parse(Console.ReadLine());
            long configs = machine.NumberConfigurations(N);
            long primes = machine.PrimeNums(configs).Count();
            Console.WriteLine(primes);
        }
    }
}

 

[Ibix]

Sorry - misread the question. You could observe that there is one way to do it solely with horizontal tiles and N-3 ways to do it with only four vertical tiles. Each choice of a position gives you two sub-problems, the range above the four verticals and the range below, so you can divide and conquer, and you can store previously solved problems to save time.

 

[wle]

I see this as equivalent to first solving the equation

4i + j = n

for non-negative integers i,j and then for the pairs where i,j>0 you have (i+j)!/(i! * j!) ways of arranging them.

This is easy: i ranges from 0 to n / 4 and j is just n - 4 * i. (According to documentation, the result of dividing two integers is another integer, so, e.g., as far as C# is concerned 11 / 4 == 2.)

I don't know C# but my guess is this means you can simplify your code computing the number of arrangements to something like

    static int NumberConfigurations(int n)
    {
        var range = Enumerable.Range(0, n / 4 + 1);
        return (from i in range
                select NumberCombinations(i, n - 4 * i)).Sum();
    }

(If you've written NumberCombinations() correctly then it should return 1 if either of its arguments are zero, so you don't need to check for this explicitly.)

Hmmmm I'm wondering whether my algorithm is even correct.

The results in your first post look wrong starting with ##N = 16##. This is probably a result of integer overflow. You compute the number of combinations by literally computing the factorial of i + j and then dividing by the factorials of i and j. The problem is that the factorial is a rapidly increasing function: the factorial of 13 is already too large to store as a signed 32 bit int, and the factorial of 21 won't fit in a signed 64 bit long. In the ##N = 16## case the code in your second post tries to compute the factorial of 13 (with i = 1 and j = 12), so you get the overflow.

One way to mitigate this (to some extent) is to rewrite your NumberCombinations() method to avoid computing excessively large intermediate integer results. (For instance, you can buy some breathing room using that ##\tfrac{(i + j)!}{i!} = (i + j) \times (i + j - 1) \times \cdots \times (i + 1)##.)

 

[robphy]

i googled the first 11 numbers in the sequence
https://oeis.org/A003269