A305461 The number of one-digit numbers, k, in base n such that k^2 and k^3 end in the same digit.

1, 2, 2, 3, 2, 4, 2, 3, 4, 4, 2, 6, 2, 4, 4, 5, 2, 8, 2, 6, 4, 4, 2, 6, 6, 4, 4, 6, 2, 8, 2, 5, 4, 4, 4, 12, 2, 4, 4, 6, 2, 8, 2, 6, 8, 4, 2, 10, 8, 12, 4, 6, 2, 8, 4, 6, 4, 4, 2, 12, 2, 4, 8, 9, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 12, 6, 4, 8, 2, 10, 10, 4, 2, 12, 4

Offset: 1

Author

Matthew Scroggs, Jun 01 2018

Keywords

• nonn
• easy
• mult

Comments

It appears that a(n) is equal to the number of factors of n, except when n cannot be divided by its multiplicative projection (A230542). - Ian Newman, Jun 01 2018

Number of solutions to x^3 - x^2 == 0 (mod n). - Andrew Howroyd, Jul 22 2018

Examples

			In base 4,
  0^2 =  0, 0^3 =   0,
  1^2 =  1, 1^3 =   1,
  2^2 = 10, 2^3 =  20,
  3^2 = 21, 3^3 = 123.
Three of these pairs have the same final digit, so a(4)=3.
		

Links

• Matthew Scroggs, Table of n, a(n) for n = 1..1000
• Matthew Scroggs, Square and cube endings.

Crossrefs

A034444 is the number of one-digit numbers, k, in base n such that k and k^2 end in the same digit.

Cf. A230542.

Programs

Haskell

a305461 n = length $ filter (\i -> (i^3 - i^2) `mod` n == 0) [0..n-1]
-- Peter Kagey, Jun 10 2018

Mathematica

Table[Count[Range@ n, ?(PowerMod[#, 2, n] == PowerMod[#, 3, n] &)], {n, 85}] (* _Michael De Vlieger, Jul 30 2018 *)
f[p_, e_] := p^Floor[e/2] + 1; a[n_] := Times @@ f @@@ FactorInteger[n]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Sep 07 2023 *)

PARI

a(n) = sum(k=0, n-1, mk = Mod(k, n); mk^2 == mk^3); \\ Michel Marcus, Jul 03 2018

PARI

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); p^(e\2) + 1)} \\ Andrew Howroyd, Jul 22 2018

Python

for base in range(1, 101):
    n = 0
    for j in range(base):
        if (j**2)%base == (j**3)%base:
            n += 1
    print(base, n)

Formula

Multiplicative with a(p^e) = p^floor(e/2) + 1 for prime p. - Andrew Howroyd, Jul 22 2018

Extensions

a(1) inserted by Andrew Howroyd, Jul 22 2018