Pentagonal numbers made from pentagonal numbers

15

4

Introduction

A pentagonal number (A000326) is generated by the formula Pn= 0.5×(3n2-n). Or you can just count the amount of dots used:

enter image description here

You can use the formula, or the gif above to find the first few pentagonal numbers:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477, etc...

Next, we need to compute the sum of x consecutive numbers.

For example, if x = 4, we need to look at Pn + Pn+1 + Pn+2 + Pn+3 (which consists of 4 terms). If the sum of the pentagonal numbers also is a pentagonal number, we will call this a pentagonal pentagon number.

For x = 4, the smallest pentagonal pentagon number is 330, which is made of 4 consecutive pentagonal numbers: 51, 70, 92, 117. So, when the input is 4, your program of function should output 330.


Task

  • When given an integer greater than 1, output the smallest pentagonal pentagon number.
  • You may provide a function or a program.
  • Note: There are no solutions for e.g. x = 3. This means that if a number cannot be made from the first 10000 pentagonal numbers, you must stop computing and output whatever fits best for you.
  • This is , so the submission with the least amount of bytes wins!

Test cases:

Input: 2
Output: 1926 (which comes from 925, 1001)

Input: 3
Output: ?

Input: 4
Output: 330 (which comes from 51, 70, 92, 117)

Input: 5
Output: 44290 (which comes from 8400, 8626, 8855, 9087, 9322)

Input: 6
Output: 651 (which comes from 51, 70, 92, 117, 145, 176)

Input: 7
Output: 287 (which comes from 5, 12, 22, 35, 51, 70, 92)

Input: 8
Output: ?

Input: 9
Output: 12105 (which comes from 1001, 1080, 1162, 1247, 1335, 1426, 1520, 1617, 1717)

Input: 10
Output: ?

Also bigger numbers can be given:

Input: 37
Output: 32782

Input: 55
Output: 71349465

Input: 71
Output: 24565290

Adnan

Posted 2015-12-21T21:00:21.953

Reputation: 41 965

4IMO it's crazy to penalise anyone who comes up with an analytic solution which can solve the harder cases by requiring them to check whether the solution is less than 10001-x – Peter Taylor – 2015-12-21T21:41:19.360

1@PeterTaylor With harder cases you mean like x = 3, which has no solutions? – Adnan – 2015-12-21T21:46:57.137

4The largest test case that yields a result: 9919 --> 496458299155 – Martin Ender – 2015-12-21T22:00:53.167

No, I mean cases which have solutions but which use larger pentagonal numbers in the sum. – Peter Taylor – 2015-12-21T22:27:33.263

1I'm not sure about the 10,000 limit: Do the numbers that build the sum have to come from the first 10,000 pentagonal numbers, but not the sum itself, or has the sum also to be within the first 10,000? – nimi – 2015-12-21T22:32:10.493

@nimi Only the numbers that build the sum have to come from the first 10000 pentagonal numbers. The sum itself may exceed this amount. – Adnan – 2015-12-21T22:33:09.173

@PeterTaylor That means you need to prove that the x value has a solution in the first place. Or else it would run infinitely on non-solution integers. – Adnan – 2015-12-21T22:45:49.313

So what's the big deal? – Peter Taylor – 2015-12-21T22:47:40.630

Answers

4

CJam, 29 bytes

6e5{)_3*(*2/}%_A4#<riew::+&1<

Try it online.

Takes a couple of seconds to run.

Explanation

First, we need to check how many pentagonal numbers we need to consider as potential sums. The sum of the first 10,000 pentagonal numbers is 500050000000. The first pentagonal number greater than that is the 577,380th.

6e5       e# 600,000 (a short number that's a bit bigger than we need).
{         e# Map this block onto every number from 0 to 599,999...
  )       e#   Increment.
  _3*(*2/ e#   Apply the pentagonal number formula given in the challenge.
}%
_         e# Make a copy.
A4#<      e# Truncate to the first 10,000 elements.
ri        e# Read input and convert to integer.
ew        e# Get sublists of that length.
::+       e# Sum each sublist.
&         e# Set intersection with all 600k pentagonal numbers computed earlier.
1<        e# Truncate to the first result.

I used a slightly modified program to find the largest inputs which yield a non-empty solution. These are all the solutions for inputs greater than 9,000:

9919 -> 496458299155
9577 -> 446991927537
9499 -> 455533474060
9241 -> 401702906276
9017 -> 429351677617

Martin Ender

Posted 2015-12-21T21:00:21.953

Reputation: 184 808

4

Lua, 142 Bytes

p={}o={}n=...for i=1,10^4 do p[i]=(3*i^2-i)/2o[p[i]]=1 end for i=0,10^4-n do s=0 for j=1,n do s=s+p[i+j]end if(o[s])then print(s)break end end

Ungolfed

p={}o={}n=tonumber(...)
for i=1,10^4 do 
    p[i]=(3*i^2-i)/2o[p[i]]=1 
end
for i=0,10^4-n do 
    s=0 
    for j=1,n do 
        s=s+p[i+j]
    end 
    if(o[s])then 
        print(s)
        break 
    end 
end

Yay for inverting tables!

Update 142 Bytes: Saved 10 bytes by removing superfluous 'tonumber' function call.

Cyv

Posted 2015-12-21T21:00:21.953

Reputation: 211

3

Haskell, 109 bytes

p=map(\n->div(3*n^2-n)2)[1..10^7]
(%)=(sum.).take
x#l|length l<x=0|elem(x%l)p=x%l|1<2=x#tail l
(#take(10^4)p)

Returns 0 if there's no pentagonal pentagon number.

Usage example (takes some time to finish): map (#take(10^4)p) [1..10] -> [1,1926,0,330,44290,651,287,0,12105,0].

It's more or less a direct implementation of the definition: if the sum of the first x elements is in the list, output it, else re-try with the tail of the list. Start with the first 10,000 pentagonal numbers, stop and return 0 if the list has less than x elements.

nimi

Posted 2015-12-21T21:00:21.953

Reputation: 34 639

3

PARI/GP, 71 bytes

I like the ispolygonal function in PARI/GP.

x->[p|p<-vector(10^4,i,sum(n=i,i+x-1,(3*n^2-n)/2)),ispolygonal(p,5)][1]

alephalpha

Posted 2015-12-21T21:00:21.953

Reputation: 23 988

3

Python 3, 144 bytes

R,P=range,list(map(lambda n:(3*n*n-n)/2,R(1,10001)))
def F(X):
 for a in R(0,len(P)-X):
    S=sum(P[a:a+X])
    if(1+(1+24*S)**.5)%6==0:print(S);break

This reverses the definition of a pentagonal number; if P(n) = (3n^2-n)/2, then a given P will be a pentagonal number iff (1+sqrt(24*P+1))/6 is an integer. (Technically, it should also look at (1-sqrt(24*P+1))/6, but that should always be negative.) Also uses spaces and tabs as two different indentation levels, as suggested here. This doesn't output anything if it can't find a pentagonal pentagonal number; I trust that's OK?

I strongly believe that someone more clever than I am could find a way to shorten this even more, probably around the for loop.

Jack Brounstein

Posted 2015-12-21T21:00:21.953

Reputation: 381

2

R, 114 100 bytes

k=.5*(3*(t=1:1e6)^2-t);z=1;for(i in 1:(1e4-(n=scan()-1)))z[i]=sum(k[i:(i+n)]);cat(intersect(k,z)[1])

ungolfed (kinda)

k=.5*(3*(t=1:1e6)^2-t)                 # map all pentagon numbers up to 1e6
z=1                                    # create a vector
for(i in 1:(1e4-(n=scan()-1))){        # from 1 to 10.000 - n loop
  z[i]=sum(k[i:(i+n)])}                # get the sum of all pentagon numbers i:(i+n)
cat(intersect(k,z)[1])                 # see which sums is a pentagon number itself, plot the first

Mutador

Posted 2015-12-21T21:00:21.953

Reputation: 1 361

2

Mathematica 85 bytes

n=577380;Intersection[#(3#-1)/2&/@Range@n,Table[#((#-1)^2+x(3#-4+3x))/2,{x,n}]][[1]]&

perfoms a quick search up to P104.

martin

Posted 2015-12-21T21:00:21.953

Reputation: 1 335

2

LabVIEW, 39 LabVIEW Primitives

No gif of it running this time.

Math node in loop creates an array of all the numbers. Take Sub-array, add elements, search for that number, if found take index and stop loop.

An invalid input puts out the highest pentagonal number.

Eumel

Posted 2015-12-21T21:00:21.953

Reputation: 2 487

2

Jelly, 30 bytes

×24‘½‘%6¬Oị
15ȷ7RÇṫ³R$zȷ.5ZSÇḢ

This code works with this version of Jelly and is equivalent to the following binary code:

0000000: 94 32 34 b2 90 b2 25 36 87 4f b1 0a 31 35 a0  .24...%6.O..15.
000000f: 37 52 92 ad 8b 52 24 7a a0 2e 35 5a 53 92 a6  7R...R$z..5ZS..

It is by far to slow and memory hungry for the online interpreter, since it checks the first 150,000,000 for pentagonality (149,995,000 happens to be the 10,000th pentagonal number).

By shortening the range to something more sensible, you can Try it online! for small enough inputs.

Idea

A known result about pentagonal numbers is that x is pentagonal if and only if sqrt(24x + 1) - 1 is divisible by 6.

Rather than computing the first 10,000 pentagonal numbers, we define a helper link that removes non-pentagonal numbers from a given array. Why? Because the latest version of Jelly that predates this challenge has no sane way to intersect lists...

Code

×24‘½‘%6¬Oị  Define the aforementioned helper link. Left argument: a (list)

×24          Multiply each list item by 24.
   ‘         Increment each product.
    ½        Apply square root to each result.
     ’       Decrement each square root.
      %6     Compute all remainders of division by 6.
        ¬    Apply logical NOT.
         O   Get the indices of ones.
          ị  Hook; get the elements of a at those indices.

15ȷ7RÇṫ³R$zȷ.5ZSÇḢ  Define the main link. Input: x

15ȷ7R               Yields [1, ..., 1.5e8].
     Ç              Apply the helper link; keep only pentagonal numbers.
       ³R$          Yield r = [1, ..., x].
      ṫ             Remove the first y-1 pentagonal numbers for each y in r.
          zȷ.5      Transpose the resulting array, padding with sqrt(10).
              Z     Transpose once more. The shifted lists have now been padded.
                    This makes sure incomplete sums (i.e., of less than x
                    pentagonal numbers) will not be integers.
               S    Compute all sums.
                Ç   Apply the helper link once more.
                 Ḣ  Select the first match, if any.

Jelly, 21 bytes (non-competing)

ȷ6Rµ²×3_¹Hµḣȷ4ṡ³ZSf¹Ḣ

The latest version of Jelly has two new features (overlapping slices and and list filtering / intersection) and a bug fix, which allows a much lower byte count.

This code works fine on my desktop computer, but it's a tad to slow for TIO's time limit. To Try it online! (for sufficiently small inputs), we have to reduce the initial range once again.

How it works

ȷ6Rµ²×3_¹Hµḣȷ4ṡ³ZSf¹Ḣ  Input: x

ȷ6R                    Yield [1, ..., 1,000,000].
   µ                   Begin a new, monadic chain.
    ²                  Square each number in the range.
     ×3                Multiply the squares by 3.
       _¹              Subtract the numbers from the range.
         H             Halve each difference.
                       This yields the first 1,000,000 pentagonal numbers.
          µ            Begin a new, monadic chain.
           ḣȷ4         Keep only the first 10,000 pentagonal numbers.
              ṡ³       Yield all overlapping slices of length x.
                ZS     Transpose and sum. This computes the sum of each slice.
                  f¹   Filter; intersect with the long list of pentagonal numbers.
                    Ḣ  Select the first match, if any.

Dennis

Posted 2015-12-21T21:00:21.953

Reputation: 196 637

0

Axiom, 157 bytes

p(n)==(3*n*n-n)quo 2;f(x)==(a:=0;for i in 1..x repeat a:=a+p(i);for j in 1..10000 repeat(p(floor((1+sqrt(1.+24*a))/6)::INT)=a=>return a;a:=a+p(j+x)-p(j));-1)

ungolfed and results

h(x:PI):INT==
   a:=0;for i in 1..x repeat a:=a+p(i) -- sum(p(i),i=1..x)
   for j in 1..10000 repeat
      p(floor((1+sqrt(1.+24*a))/6)::INT)=a=>return a
      a:=a+p(j+x)-p(j)
   -1

(5) -> [[i,f(i)] for i in 1..10]
   (5)
   [[1,1], [2,1926], [3,- 1], [4,330], [5,44290], [6,651], [7,287], [8,- 1],
    [9,12105], [10,- 1]]
                                                  Type: List List Integer

esplenation: We can find n using the result "a", see below

a=(3*n^2-n)/2 => 3*n^2-n-2*a=0 => n=floor((1+sqrt(1.+24*a))/6)::INT

[use 1+sqrt(...) because n>0]

This above means that if exist one n0 such that

p(n0)=a 

than

n0=floor((1+sqrt(1.+24*a))/6)::INT

Afher that we have to prove that p(n0)=a for to be sure (because it is not always so)

But the main trick would be doing the sum

a:=sum(p(i),i=1..x) [x elements sum] 

only at the start, and find the next x elements sum simply using

a=a+p(x+1)-p(1)=sum(p(i), i=2..x+1)

and so on for the other sums (using above in the statement a:=a+p(j+x)-p(j) ). This means it is not necessary one number x element sum inside the loop... ..

RosLuP

Posted 2015-12-21T21:00:21.953

Reputation: 3 036

0

Javascript 93 bytes

p=i=>i>0&&3*i*i-i>>1
f=(x,i=1,t=0)=>i<1e4?(24*(t+=p(i)-p(i-x))+1)**.5%6==5&i>x?t:f(x,i+1,t):0

console.log(f(4))
console.log(f(5))
console.log(f(6))
console.log(f(7))
console.log(f(8))
console.log(f(9919)==496458299155)
console.log(f(9577)==446991927537)
console.log(f(9499)==455533474060)
console.log(f(9241)==401702906276)
console.log(f(9017)==429351677617)
console.log(f(9))
console.log(f(10))

DanielIndie

Posted 2015-12-21T21:00:21.953

Reputation: 1 220

0

Python 2, 128 124 bytes

X=input();N=S=0
while all(S-(3*n*n-n)/2for n in range(S)):N+=1;S=sum(3*(n+N)**2-n-N>>1for n in range(X));N<1e4or 0/0
print S

Try it online!

Jonathan Frech

Posted 2015-12-21T21:00:21.953

Reputation: 6 681