(49G & 38G & Prime) OEIS A111138: No Short Description

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (49G & 38G & Prime) OEIS A111138: No Short Description (/thread-9514.html)

(49G & 38G & Prime) OEIS A111138: No Short Description - Gerald H - 11-17-2017 04:35 AM

For natural number input N the programme below returns the Nth element of the series

https://oeis.org/A111138

described as

"For a subgroup H of order p^n (p an odd prime) of the subgroup generated by all commutators [x_j,x_i] in the relatively free group F of class three and exponent p, freely generated by x_1, x_2,..., x_k, (k sufficiently large) the minimum size of the subgroup of [H,F] of F_3 is p^{kn - a(n)}.
The sequence arises when finding a purely numerical sufficient condition for the capability of p-groups of class two and exponent p, where p is an odd prime."

Whatever you make of the description, the programme below is fairly simple but slow.

Could everyone please try to find a faster programme &/or a better algorithm?

The sub-programme ID ISQRT is here

http://www.hpmuseum.org/forum/thread-3837.html?highlight=square+root

Size: 179.5

CkSum: # 36635d

Code:
::
  CK1&Dispatch
  # FF
  ::
    ZINT 0
    SWAP
    BEGIN
    DUP
    ZINT 3
    Z>
    WHILE
    ::
      ZINT 1
      FPTR2 ^RSUBext
      DUP
      ZINT 8
      FPTR2 ^RMULText
      ZINT 1
      FPTR2 ^RADDext
      ID ISQRT
      DROP
      ZINT 1
      FPTR2 ^RSUBext
      DUP
      FPTR2 ^ZAbs
      FPTR2 ^QIsZero?
      ?SEMI
      ZINT 2
      FPTR2 ^ZQUOText
      FPTR2 ^RSUBext
      DUPUNROT
      FPTR2 ^RADDext
      SWAP
    ;
    REPEAT
    ZINT 3
    EQUAL
    NOT?SEMI
    ZINT 1
    FPTR2 ^RADDext
  ;
;


RE: (49G) OEIS A111138: No Short Description - Arno K - 11-18-2017 09:04 AM

I made an algorithm by myself, my apologies if it is similar to yours (I hope not as you don't seem to use a root), my capabilities in reading sysrpl are limited, the program is for the prime and a MAKELIST(A111138(x),x,1,64) provides exactly the same list as in OEIS, it is quite fast and the algorithm is visible (one of the reasons for which I put my 50g into a drawer).
Code:
#cas
A111138(n):=
BEGIN
local m,s;
IF n<3 THEN RETURN 0;END;
IF n≤4 THEN RETURN 1;END;
m:=FLOOR(0.5+0.5*√(8*n+1));
WHILE m*(m-1)≥2*n DO
m:=m-1;
END;
s:=n-m*(m-1)/2;
  return COMB(m,3)+COMB(s,2);
END;
#end
Arno

RE: (49G) OEIS A111138: No Short Description - Gerald H - 11-18-2017 09:52 AM

Congratulations, Arno K, a very nice programme for which you should certainly not apologize.

Here a programme for the 38G.

The complications with the IFTE structures are due to the COMB function in the 38G returning an error for

COMB(a,b)

if a<b, whereas the Prime returns 0.

A111138P

Code:
Ans►N:
IF
Ans==1
THEN
0:
ELSE
ROUND(√(2*Ans),0)►R:
N-COMB(Ans,2):
IFTE(Ans>1,COMB(Ans,2),0)+IFTE(R>2,COMB(R,3),0):
END:


RE: (49G) OEIS A111138: No Short Description - Gerald H - 11-18-2017 10:40 AM

On the 49G the 38G programme works nicely as:

Code:
« DUPDUP 2. * √ 0.
RND R→I DUP 3 COMB
UNROT 2 COMB - 2
COMB + SWAP DROP
»

Fortunately, from the 49G on, for

a<b

COMB(a,b)

returns

0

rather than an error. 42S & 48G return error.

RE: (49G) OEIS A111138: No Short Description - Gerald H - 11-18-2017 11:13 AM

Here a SysRPL version of the programme above.

ID SQRT0

finds the closest integer square root & is available here

http://www.hpmuseum.org/forum/thread-8992.html?highlight=square+root

PTR 2EF19

is internal COMB, same address since 1.19-6.

Size: 77.

CkSum: # 6728h

Code:
::
  CK1&Dispatch
  # FF
  ::
    DUPDUP
    FPTR2 ^RADDext
    ID SQRT0
    DUP
    ZINT 3
    PTR 2EF19
    3UNROLL
    ZINT 2
    PTR 2EF19
    FPTR2 ^RSUBext
    ZINT 2
    PTR 2EF19
    FPTR2 ^RADDext
  ;
;


RE: (49G) OEIS A111138: No Short Description - Gerald H - 11-18-2017 11:28 AM

And here a programme to insert symbolics in the Sequence App of the 38G to produce the series:

Code:
RECURSE(U,IFTE(U3(N)>1,COMB(U3(N),2),0)+IFTE(U2(N)>2,COMB(U2(N),3),0),0,0)►U1(N):
CHECK 1:
RECURSE(U,ROUND(√(2*N),0),1,2)►U2(N):
RECURSE(U,N-COMB(U2(N),2),0,0)►U3(N):
RECURSE(U,U3(N)-1,0,0)►U4(N):
CHECK 4:


RE: (49G & 38G & Prime) OEIS A111138: No Short Description - Gerald H - 11-19-2017 03:25 AM

Another programme for the 38G using the COMB0 programme available here

http://www.hpmuseum.org/forum/thread-9530.html

Code:
Ans►N:
ROUND(√(2*Ans),0)►R:
(Ans,2):
RUN COMB0:
(N-Ans,2):
RUN COMB0:
Ans►T:
(R,3):
RUN COMB0:
Ans+T:


RE: (49G & 38G & Prime) OEIS A111138: No Short Description - John Keith - 07-05-2019 08:57 AM

My apologies for bringing up an old thread, but I was looking at the OEIS page and i was struck by the last comment: "Partial sums of A002262." This inspired the following program which returns a list of the first T(n) terms, where T(n) is the nth triangular number.

It is reasonably fast: an input of 45 returns the first 1035 terms in about 4.14 seconds on my HP 50. The program requires the ListExt and GoferLists libraries. It could be rewritten without them but the program would be longer and slower.

Code:

\<< \-> n
  \<< 0 n 1 -
    FOR k 0 k LSEQR
    NEXT n \->LIST LXIL
    \<< +
    \>> Scanl1
  \>>
\>>