8
\$\begingroup\$

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. enter image description here

    • 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:

enter image description here

  • And the nth p-gonal pyramid number is:

enter image description here

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you add some more detail about what a cannonball number is? It's not entirely clear from your description. \$\endgroup\$ – DJMcMayhem Jul 6 '16 at 16:45
  • 3
    \$\begingroup\$ Is it guaranteed that there is an answer for any n? If not, what is the range of n you'll be using? \$\endgroup\$ – Geobits Jul 6 '16 at 16:47
  • \$\begingroup\$ @DrGreenEggsandIronMan Edited to make a definition. n-gonal and n-gonal pyramid numbers shouldn't need defining. \$\endgroup\$ – Qwerp-Derp Jul 6 '16 at 16:51
  • \$\begingroup\$ @Geobits Edited to make a range instead of using memory. \$\endgroup\$ – Qwerp-Derp Jul 6 '16 at 16:51
  • 1
    \$\begingroup\$ @DerpfacePython TL;DR: Cannonball numbers quite rare. Look for yourself. \$\endgroup\$ – Rɪᴋᴇʀ Jul 6 '16 at 16:57
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ummm... this might be a bit too late to say... but... my formula was wrong. You just need to change the polygonal formula. \$\endgroup\$ – Qwerp-Derp Jul 10 '16 at 16:05
  • \$\begingroup\$ @DerpfacePython Thanks for catching that. \$\endgroup\$ – TheBikingViking Jul 10 '16 at 17:50
1
\$\begingroup\$

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>');
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wait... is the i in your formula the imaginary number i? \$\endgroup\$ – Qwerp-Derp Jul 13 '16 at 16:57
  • \$\begingroup\$ Oops, sorry. i is supposed to be n. I had different notation littered in my research. I can't imagine using an imaginary number for this problem, and I definitely can't imagine using it in C. \$\endgroup\$ – user55852 Jul 13 '16 at 17:09
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.