The   totient   function is also known as:

   Euler's totient function
   Euler's phi totient function
   phi totient function
    Φ    function   (uppercase Greek phi)
    φ     function   (lowercase Greek phi)


Definitions   (as per number theory)

The totient function:

   counts the integers up to a given positive integer   n   that are relatively prime to   n
   counts the integers   k   in the range   1 ≤ k ≤ n   for which the greatest common divisor   gcd(n,k)   is equal to   1
   counts numbers   ≤ n   and   prime to   n


If the totient number   (for N)   is one less than   N,   then   N   is prime.



Task

Create a   totient   function and:

   Find and display   (1 per line)   for the 1st   25   integers:
   the integer   (the index)
   the totient number for that integer
   indicate if that integer is prime
   Find and display the   count   of the primes up to          100
   Find and display the   count   of the primes up to       1,000
   Find and display the   count   of the primes up to     10,000
   Find and display the   count   of the primes up to   100,000     (optional)
Show all output here.



Related task

   Perfect totient numbers


Also see

   Wikipedia: Euler's totient function.
   MathWorld: totient function.
   OEIS: Euler totient function phi(n).


 
/* ARM assembly Raspberry PI or android with termux */
/*  program totient.s   */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
.equ MAXI,      25
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessNumber:       .asciz " number @ totient @  @ \n"
szCarriageReturn:   .asciz "\n"
szMessPrime:        .asciz " is prime."
szMessSpace:        .asciz " "
szMessCounterPrime: .asciz "Number of primes to @ : @ \n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
sZoneConv:           .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:
    mov r4,#1                   @ start number
1: 
    mov r0,r4
    bl totient                  @ compute totient
    mov r5,r0
    mov r0,r4
    bl isPrime                  @ control if number is prime
    mov r6,r0
    mov r0,r4                   @ display result
    ldr r1,iAdrsZoneConv
    bl conversion10             @ call décimal conversion
    ldr r0,iAdrszMessNumber
    ldr r1,iAdrsZoneConv        @ insert conversion in message
    bl strInsertAtCharInc
    mov r7,r0
    mov r0,r5
    ldr r1,iAdrsZoneConv
    bl conversion10             @ call décimal conversion
    mov r0,r7
    ldr r1,iAdrsZoneConv        @ insert conversion in message
    bl strInsertAtCharInc
    mov r7,r0
    cmp r6,#1
    ldreq r1,iAdrszMessPrime
    ldrne r1,iAdrszMessSpace
    mov r0,r7
    bl strInsertAtCharInc
    bl affichageMess             @ display message
 
    add r4,r4,#1                 @ increment number
    cmp r4,#MAXI                 @ maxi ?
    ble 1b                       @ and loop
 
    mov r4,#2                    @ first number 
    mov r5,#0                    @ prime counter 
    ldr r6,iCst1000              @ load constantes
    ldr r7,iCst10000
    ldr r8,iCst100000
2:
    mov r0,r4
    bl isPrime
    cmp r0,#0
    beq 3f
    add r5,r5,#1
3:
    add r4,r4,#1
    cmp r4,#100
    bne 4f
    mov r0,#100
    mov r1,r5
    bl displayCounter
    b 7f
4:
    cmp r4,r6        @ 1000
    bne 5f
    mov r0,r6
    mov r1,r5
    bl displayCounter
    b 7f
5:
    cmp r4,r7        @ 10000
    bne 6f
    mov r0,r7
    mov r1,r5
    bl displayCounter
    b 7f
6:
    cmp r4,r8        @ 100000
    bne 7f
    mov r0,r8
    mov r1,r5
    bl displayCounter
7:
    cmp r4,r8
    ble 2b                      @ and loop
 
100:                            @ standard end of the program 
    mov r0, #0                  @ return code
    mov r7, #EXIT               @ request to exit program
    svc #0                      @ perform the system call
iAdrszCarriageReturn:    .int szCarriageReturn
iAdrsZoneConv:           .int sZoneConv  
iAdrszMessNumber:        .int szMessNumber
iAdrszMessCounterPrime:  .int szMessCounterPrime
iAdrszMessPrime:         .int szMessPrime
iAdrszMessSpace:         .int szMessSpace
iCst1000:                .int 1000
iCst10000:               .int 10000
iCst100000:              .int 100000
/******************************************************************/
/*    display counter                                             */ 
/******************************************************************/
/* r0 contains limit  */
/* r1 contains counter */
displayCounter:
    push {r1-r3,lr}           @ save  registers 
    mov r2,r1
    ldr r1,iAdrsZoneConv
    bl conversion10             @ call décimal conversion
    ldr r0,iAdrszMessCounterPrime
    ldr r1,iAdrsZoneConv        @ insert conversion in message
    bl strInsertAtCharInc
    mov r3,r0
    mov r0,r2
    ldr r1,iAdrsZoneConv
    bl conversion10             @ call décimal conversion
    mov r0,r3
    ldr r1,iAdrsZoneConv        @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess
100:
    pop {r1-r3,pc}             @ restaur registers
/******************************************************************/
/*     compute totient of number                                  */ 
/******************************************************************/
/* r0 contains number  */
totient:
    push {r1-r5,lr}           @ save  registers 
    mov r4,r0                 @ totient
    mov r5,r0                 @ save number
    mov r1,#0                 @ for first divisor
1:                            @ begin loop
    mul r3,r1,r1              @ compute square
    cmp r3,r5                 @ compare number
    bgt 4f                    @ end 
    add r1,r1,#2              @ next divisor
    mov r0,r5
    bl division      
    cmp r3,#0                 @ remainder null ?
    bne 3f
2:                            @ begin loop 2
    mov r0,r5
    bl division
    cmp r3,#0
    moveq r5,r2               @ new value = quotient
    beq 2b
 
    mov r0,r4                 @ totient
    bl division
    sub r4,r4,r2              @ compute new totient
3:
    cmp r1,#2                 @ first divisor ?
    moveq r1,#1               @ divisor = 1
    b 1b                      @ and loop
4:
    cmp r5,#1                 @ final value > 1
    ble 5f
    mov r0,r4                 @ totient
    mov r1,r5                 @ divide by value
    bl division
    sub r4,r4,r2              @ compute new totient
5:
 
    mov r0,r4
100:
    pop {r1-r5,pc}             @ restaur registers
 
/***************************************************/
/*   check if a number is prime              */
/***************************************************/
/* r0 contains the number            */
/* r0 return 1 if prime  0 else */
@2147483647
@4294967297
@131071
isPrime:
    push {r1-r6,lr}    @ save registers 
    cmp r0,#0
    beq 90f
    cmp r0,#17
    bhi 1f
    cmp r0,#3
    bls 80f            @ for 1,2,3 return prime
    cmp r0,#5
    beq 80f            @ for 5 return prime
    cmp r0,#7
    beq 80f            @ for 7 return prime
    cmp r0,#11
    beq 80f            @ for 11 return prime
    cmp r0,#13
    beq 80f            @ for 13 return prime
    cmp r0,#17
    beq 80f            @ for 17 return prime
1:
    tst r0,#1          @ even ?
    beq 90f            @ yes -> not prime
    mov r2,r0          @ save number
    sub r1,r0,#1       @ exposant n - 1
    mov r0,#3          @ base
    bl moduloPuR32     @ compute base power n - 1 modulo n
    cmp r0,#1
    bne 90f            @ if <> 1  -> not prime
 
    mov r0,#5
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#7
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#11
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#13
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#17
    bl moduloPuR32
    cmp r0,#1
    bne 90f
80:
    mov r0,#1        @ is prime
    b 100f
90:
    mov r0,#0        @ no prime
100:                 @ fin standard de la fonction 
    pop {r1-r6,lr}   @ restaur des registres
    bx lr            @ retour de la fonction en utilisant lr 
/********************************************************/
/*   Calcul modulo de b puissance e modulo m  */
/*    Exemple 4 puissance 13 modulo 497 = 445         */
/*                                             */
/********************************************************/
/* r0  nombre  */
/* r1 exposant */
/* r2 modulo   */
/* r0 return result  */
moduloPuR32:
    push {r1-r7,lr}    @ save registers  
    cmp r0,#0          @ verif <> zero 
    beq 100f
    cmp r2,#0          @ verif <> zero 
    beq 100f           @ TODO: vérifier les cas erreur
1:
    mov r4,r2          @ save modulo
    mov r5,r1          @ save exposant 
    mov r6,r0          @ save base
    mov r3,#1          @ start result
 
    mov r1,#0          @ division de r0,r1 par r2
    bl division32R
    mov r6,r2          @ base <- remainder
2:
    tst r5,#1          @  exposant even or odd
    beq 3f
    umull r0,r1,r6,r3
    mov r2,r4
    bl division32R
    mov r3,r2          @ result <- remainder
3:
    umull r0,r1,r6,r6
    mov r2,r4
    bl division32R
    mov r6,r2          @ base <- remainder
 
    lsr r5,#1          @ left shift 1 bit
    cmp r5,#0          @ end ?
    bne 2b
    mov r0,r3
100:                   @ fin standard de la fonction
    pop {r1-r7,lr}     @ restaur des registres
    bx lr              @ retour de la fonction en utilisant lr    
 
/***************************************************/
/*   division number 64 bits in 2 registers by number 32 bits */
/***************************************************/
/* r0 contains lower part dividende   */
/* r1 contains upper part dividende   */
/* r2 contains divisor   */
/* r0 return lower part quotient    */
/* r1 return upper part quotient    */
/* r2 return remainder               */
division32R:
    push {r3-r9,lr}    @ save registers
    mov r6,#0          @ init upper upper part remainder  !!
    mov r7,r1          @ init upper part remainder with upper part dividende
    mov r8,r0          @ init lower part remainder with lower part dividende
    mov r9,#0          @ upper part quotient 
    mov r4,#0          @ lower part quotient
    mov r5,#32         @ bits number
1:                     @ begin loop
    lsl r6,#1          @ shift upper upper part remainder
    lsls r7,#1         @ shift upper  part remainder
    orrcs r6,#1        
    lsls r8,#1         @ shift lower  part remainder
    orrcs r7,#1
    lsls r4,#1         @ shift lower part quotient
    lsl r9,#1          @ shift upper part quotient
    orrcs r9,#1
                       @ divisor sustract  upper  part remainder
    subs r7,r2
    sbcs  r6,#0        @ and substract carry
    bmi 2f             @ négative ?
 
                       @ positive or equal
    orr r4,#1          @ 1 -> right bit quotient
    b 3f
2:                     @ negative 
    orr r4,#0          @ 0 -> right bit quotient
    adds r7,r2         @ and restaur remainder
    adc  r6,#0 
3:
    subs r5,#1         @ decrement bit size 
    bgt 1b             @ end ?
    mov r0,r4          @ lower part quotient
    mov r1,r9          @ upper part quotient
    mov r2,r7          @ remainder
100:                   @ function end
    pop {r3-r9,lr}     @ restaur registers
    bx lr  
 
 
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 