Cannonball Conundrum

Question

Your task is to, with an input number p, find the smallest positive cannonball number of order p that is NOT 1.

Definition

A cannonball number (of order p) is a number which is both:

• An p-gonal number (See this page).

• and an p-gonal pyramid number.

  • The nth p-gonal pyramid number is the sum of the 1st to nth p-gonal numbers.
    • (e.g. 4th square pyramid number = 1 + 4 + 9 + 16 = 30)

  • The picture below represents the 4th square pyramid number, as a square pyramid.

  • For more info, visit this link.

The cannonball number of order 3, for example, is 10, because it is:

• The fourth triangle number (1 + 2 + 3 + 4 = 10)
• and the third triangular pyramid number. (1 + 3 + 6 = 10)

Formulas

NOTE: If you can find (or make) more useful formulae than my ones here, please post it here (or message me on the question chat thing).

• If you're interested, the formula for the nth p-gonal number is:

• And the nth p-gonal pyramid number is:

Specs

• p is guaranteed to be larger than 2.
• The program must check values for a solution for p up to (and including) 2^16. Your program may do anything if no solutions are found for p.
• Only positive indices for n.

Test cases

• 3 outputs 10 (4th triangle number, 3rd triangle pyramid number)
• 4 outputs 4900 (70th square number, 24th square pyramid number)

This is code-golf, so shortest answer in bytes wins.

Note: If you do post a solution, please include a description of how the code works.

Should I start a bounty for a solution which is better and doesn't use my formulae?

Answer 1

Python 3, 129 127 bytes

def f(p):
 x=2
 while 1:
  for i in range(x*x):
   if i//x*((p-2)*i//x+4-p)/2==i%x*(i%x+1)*((p-2)*i%x+5-p)/6==x:return x
  x+=1

A function that takes input via argument and returns the output.

This is an extremely naïve brute force, and takes a very long time for even moderately large p; the execution time will be ridiculous for anything approaching the given maximum for p of 2^16, but there is no reason why the program would not work, given sufficient time.

There are probably far shorter and faster ways of doing this, but I thought it would be good to post something to get this started off.

How it works

The return value x is initialised to 2, and then the program simply loops over all the p-gonal and p-gonal pyramidal numbers up to order x. If the current p-gonal and p-gonal pyramidal numbers, calculated using the formulas, are equal to each other and to x, then x must be the relevant cannonball number and this is returned. Else, x is incremented, and the program tries again for the new value of x.

In terms of golfing, a Cartesian product is used to collapse the two for-loops for the p-gonal and p-gonal pyramidal numbers into a single loop, and the formulas were factorised further to save a few bytes.

Answer 2

JavaScript, 111 98 bytes

f=n=>{for(b=c=g=1;b++;)for(p=b*(b*3+b*b*(n-2)-n+5)/6;g<p;c++)if(p==(g=c*(c*n-c-c-n+4)/2))return p}

ungolfed

f=n=>{
for(b=2,c=g=1;b<1e6;b++)    // run index b from 2 (to 100k)
    for(
        p=(b*b*3+b*b*b*(n-2)-b*(n-5))/6 // p=the b-th n-pyramidal number
        ;g<p&&c<1e6;c++)   // run while n-gonal is lower than n-pyramidal (and c below 100k)
        if(p==(
            g=(c*c*(n-2)-c*(n-4))/2     // g=the c-th n-gonal number
        )) return p                     // if they are equal, return
}

c is not reinitialized in the inner loop because the next p[b] is definitely larger than the current g[c] (so we have to move on anyway)

examples

samples=[3,4,6,8,10,11,14,17,23,26,30,32,35,41,43,50,88]
for(i in samples) document.write('n='+(n=samples[i])+': '+f(n)+'<br>');

Answer 3

C, 107 bytes

#define X(x)(1+p/2.0*x)*++x
c(p,m,n,a,b){m=n=a=b=1;p-=2;do if(a>b)b+=X(n);else a=X(m);while(a^b);return a;}

Ungolfed with test parameters:

#include <stdio.h>

#define X(x)(1+p/2.0*x)*++x
int c(int p)
{
    int m = 1, n = 1, a = 1, b = 1;
    p -= 2;
    do
        if(b < X(m))
            b += X(n);
        else
            a = X(m);
    while(a != b);
    return a;
}

int main()
{
    printf("%d\n", c(3));
    printf("%d\n", c(4));
}

This uses the fact that the n-th p-gonal number can be defined as n(1+(p-2)(n-1)/2) and the pyramid number is the sum of the aforementioned numbers.

I think it can be further golfed, given that it's not really necessary for variable a to be saved.

Answer 4

old PHP program, 115 106 bytes

^{+16 for current PHP, see below}

<?for($b=2;1;$b++)for($p=$b*($b*3+$b*$b*($n-2)-$n+5)/6;$g<$p;++$c)if($p==$g=$c*($c*$n-2*$c-$n+4)/2)echo$p;

• loops forever
• usage: with PHP<4.2: run from browser with <scriptpath>?n=<number>
  with PHP<5.4, add register_globals=1 to php.ini (+18 ?)
• see my JavaScript answer for description
• +10 for PHP>=5.4: replace 1 with $n=$_GET[n]. Or replace 1 with $n=$argv[1], run php -f <filename> <number>.
• +6 for finite loop on success: replace echo$p with die(print$p)

• +/- 0 for function:

  function f($n){for($b=2;1;$b++)for($p=$b*($b*3+$b*$b*($n-2)-$n+5)/6;$g<$p;++$c)if($p==$g=$c*($c*$n-2*$c-$n+4)/2)return$p;}
  

  loops forever if it finds nothing. Replace 1 with $p<1e6 to break at 100k or with $p<$p+1 to loop until integer overflow. (tested with PHP 5.6)

examples (on function)

$samples=[3,4,6,8,10,11,14,17,23,26,30,32,35,41,43,50,88];
foreach($samples as $n)echo "<br>n=$n: ", f($n);

examples output

n=3: 10
n=4: 4900
n=6: 946
n=8: 1045
n=10: 175
n=11: 23725
n=14: 441
n=17: 975061
n=23: 10680265
n=26: 27453385
n=30: 23001
n=32: 132361021
n=35: 258815701
n=41: 55202400
n=43: 245905
n=50: 314755
n=88: 48280