Request for "Decimal Period of 1/X in Base Y" program

+- HP Forums (http://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: HP Prime (/forum-5.html)
+--- Thread: Request for "Decimal Period of 1/X in Base Y" program (/thread-3212.html)

Request for "Decimal Period of 1/X in Base Y" program - Joe Horn - 02-27-2015 12:13 AM

EDIT: This discussion's original title was:
Request for "Multiplicative Order of Y (mod X)" program
... but my actual goal is the "decimal period of 1/X in base Y", which I wrongly thought was the same thing. Hence the confusion as the discussion progresses below...

Has anybody already written a Prime program to calculate the Number Theory value of "the multiplicative order of Y (mod X)"?

One application of this concept is found in repeating decimal numbers. For example, 1/13 = 0.076923076923... where "076923" repeats forever. Notice that the repeating section of 1/13 is 6 digits long. In Number Theory, they express this as "the multiplicative order of 10 (mod 13) = 6" with the 10 coming from the fact that decimal numbers (as the name implies) use base 10. "Multiplicative order" is often shortened to just "order".

Another example: In hexadecimal, 1/Dh (that's 1/13 in decimal) = 0.13B13B13B...h, where the three hex digits "13B" repeat forever. So the order of 16 (mod 13) = 3.

In Mathematica, it's implemented as MultiplicativeOrder[y,x].

Thanks in advance to anybody who has already programmed their Prime to find the order of Y (mod X). It shouldn't be too hard, since Prime has EULER, IDIVIS, and MODPOW built in.

RE: Request for "Multiplicative Order of Y (mod X)" program - Thomas Ritschel - 02-27-2015 02:49 AM

Here is a simple non-CAS variant:
Code:
EXPORT MultiplicativeOrder(a,base)
BEGIN
  LOCAL k:=0;
  LOCAL res:=1;
  REPEAT
    res:=res*base;
    k:=k+1;
    res:=res MOD a;
  UNTIL res==1;
  RETURN(k);
END;


RE: Request for "Multiplicative Order of Y (mod X)" program - Gerald H - 02-27-2015 03:35 AM

(02-27-2015 12:13 AM)Joe Horn Wrote:  Has anybody already written a Prime program to calculate the Number Theory value of "the multiplicative order of Y (mod X)"?

One application of this concept is found in repeating decimal numbers. For example, 1/13 = 0.076923076923... where "076923" repeats forever. Notice that the repeating section of 1/13 is 6 digits long. In Number Theory, they express this as "the multiplicative order of 10 (mod 13) = 6" with the 10 coming from the fact that decimal numbers (as the name implies) use base 10. "Multiplicative order" is often shortened to just "order".

Another example: In hexadecimal, 1/Dh (that's 1/13 in decimal) = 0.13B13B13B...h, where the three hex digits "13B" repeat forever. So the order of 16 (mod 13) = 3.

In Mathematica, it's implemented as MultiplicativeOrder[y,x].

Thanks in advance to anybody who has already programmed their Prime to find the order of Y (mod X). It shouldn't be too hard, since Prime has EULER, IDIVIS, and MODPOW built in.

Are you only interested in integer values of X & Y?

IF you're only interested in integer values for X & Y, this 50G prog does the job:

Input:

2: Modulus

1: Number whose orderis to be calculated

Returns the order you requested.

::
CK2&Dispatch
# FFFF
::
2DUP
FPTR2 ^ZGCDext
FPTR2 ^ZIsOne?
NOTcase2drop
Z0_
OVER
FPTR2 ^QMod
DUPUNROT
OVER
FPTR2 ^EULER
FPTR2 ^ZFACTO
ROTDROP
DUPLENCOMP
#2/
ZERO_DO
DUPUNROT
INDEX@
#2*
#1+DUP
#1+
SUBCOMP
INCOMPDROP
OVERUNROT
COERCE
FPTR2 ^PPow#
ROTSWAP
FPTR2 ^ZQUOText
4ROLLOVER
6PICK
FPTR2 ^ModPow
5PICK
FPTR2 ^QMod
BEGIN
FPTR2 ^DupZIsOne?
NOT_WHILE
::
3PICK
6PICK
FPTR2 ^ModPow
5PICK
FPTR2 ^QMod
SWAP3PICK
FPTR2 ^QMul
SWAP
;
REPEAT
DROPSWAPDROP
4PICKSWAP
ROT
LOOP
DROP
4UNROLL3DROP
;
;

I'm sure you Prime buffs won't have much trouble translating that into Prime.

RE: Request for "Multiplicative Order of Y (mod X)" program - Joe Horn - 02-27-2015 10:01 AM

(02-27-2015 02:49 AM)Thomas Ritschel Wrote:  Here is a simple non-CAS variant:

Thanks, Thomas! Now I gotta turn your program into an exact-integer CAS program.

(02-27-2015 03:57 AM)Gerald H Wrote:  IF you're only interested in integer values for X & Y, this 50G prog does the job: ...

Here's the URPL program I currently use on the 50g:

Code:
<<
WHILE DUP PICK3 GCD DUP 1 >
REPEAT /
END DROP DUP MODSTO EULER DIVIS DUP2 POWMOD 1 POS GET NIP
>>
BYTES: 11.5 #F350h
Input: Y, X (exact mode, of course)
Output: order of Y (mod X)

RE: Request for "Multiplicative Order of Y (mod X)" program - Gerald H - 03-01-2015 02:18 AM

ie Write fraction in lowest terms, a/b, remove factors of 2 & 5 from b, call this c, then calculate order of 10 modulo c - that, I hope, does the trick, ie returns number of repeating digits.

::
CK2&Dispatch
# FFFF
::
FPTR2 ^ZTrialDiv2
DROP
BEGIN
DUP
Z5_
FPTR2 ^ZMod
FPTR2 ^QIsZero?
WHILE
::
Z5_
FPTR2 ^ZQUOText
;
REPEAT
DUPUNROT
FPTR2 ^ZGCDext
FPTR2 ^ZQUOText
FPTR2 ^DupZIsOne?
casedrop
Z0_
Z10_
xORD
;
;