(49G & 38G & Prime) OEIS A111138: No Short Description
11-17-2017, 09:35 AM (This post was last modified: 11-18-2017 04:30 PM by Gerald H.)
Post: #1
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
(49G & 38G & Prime) OEIS A111138: No Short Description
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

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   ; ;
11-18-2017, 02:04 PM (This post was last modified: 11-18-2017 05:43 PM by Arno K.)
Post: #2
 Arno K Senior Member Posts: 442 Joined: Mar 2015
RE: (49G) OEIS A111138: No Short Description
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
11-18-2017, 02:52 PM (This post was last modified: 11-18-2017 04:49 PM by Gerald H.)
Post: #3
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G) OEIS A111138: No Short Description
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:
11-18-2017, 03:40 PM
Post: #4
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G) OEIS A111138: No Short Description
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.
11-18-2017, 04:13 PM
Post: #5
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G) OEIS A111138: No Short Description
Here a SysRPL version of the programme above.

ID SQRT0

finds the closest integer square root & is available here

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   ; ;
11-18-2017, 04:28 PM
Post: #6
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G) OEIS A111138: No Short Description
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:
11-18-2017, 04:33 PM
Post: #7
 Arno K Senior Member Posts: 442 Joined: Mar 2015
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
I hope your new program runs faster than the old one.
Arno
11-18-2017, 04:48 PM
Post: #8
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
Yes, it certainly does, & I believe faster than yours, if you could translate it to run on Prime.
11-18-2017, 05:38 PM (This post was last modified: 11-18-2017 05:57 PM by Arno K.)
Post: #9
 Arno K Senior Member Posts: 442 Joined: Mar 2015
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
Quite clear, you leave out the loop to determine the best m, perhaps that will be necessary if n increases, I don't know as I haven't checked that.
Arno
Edit: I now verified that I can leave out that loop, as it never will be executed, but I will leave the source above as it is.
11-18-2017, 06:04 PM
Post: #10
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
It might be a good idea to publish your finished programme in the Prime Software Library.
11-18-2017, 06:27 PM (This post was last modified: 11-18-2017 06:28 PM by Arno K.)
Post: #11
 Arno K Senior Member Posts: 442 Joined: Mar 2015
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
Have you checked n=7? I get 7 on my Prime instead of 4.
11-18-2017, 07:14 PM (This post was last modified: 11-18-2017 07:15 PM by Gerald H.)
Post: #12
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
Input

7

returns

4

on all my programmes.
11-18-2017, 08:00 PM (This post was last modified: 11-18-2017 08:32 PM by Arno K.)
Post: #13
 Arno K Senior Member Posts: 442 Joined: Mar 2015
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
Got it: 0. RND rounds nearest, FLOOR clearly down.
Arno
11-19-2017, 08:25 AM
Post: #14
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
Another programme for the 38G using the COMB0 programme available here

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:
07-05-2019, 01:57 PM (This post was last modified: 07-05-2019 01:59 PM by John Keith.)
Post: #15
 John Keith Senior Member Posts: 617 Joined: Dec 2013
RE: (49G & 38G & Prime) OEIS A111138: No Short Description
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   \>> \>>
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)