A054717 Number of powers of 9 modulo n.

1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 5, 2, 3, 3, 3, 2, 8, 2, 9, 2, 4, 5, 11, 2, 10, 3, 3, 3, 14, 3, 15, 4, 6, 8, 6, 2, 9, 9, 4, 2, 4, 4, 21, 5, 3, 11, 23, 3, 21, 10, 9, 3, 26, 3, 10, 3, 10, 14, 29, 3, 5, 15, 4, 8, 6, 6, 11, 8, 12, 6, 35, 2, 6, 9, 11, 9, 15, 4, 39, 2, 3, 4, 41, 4, 8, 21, 15, 5, 44, 3, 3

Offset: 1

Author

Henry Bottomley, Apr 20 2000

Keywords

• easy
• nonn

Examples

			Take the sequence 1, 9, 81, 729, ... and reduce mod n; count distinct terms. For n = 5 we get 1, 4, 1, 4, ... so a(5) = 2.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from David W. Wilson)

Crossrefs

Cf. A007740.

Cf. A054703 (base 2), A054704 (3), A054705 (4), A054706 (5), A054707 (6), A054708 (7), A054709 (8), A054710 (10), A351524 (11), A054712 (12), A054713 (13), A054714 (14), A054715 (15), A054716 (16).

Programs

Mathematica

With[{p9=9^Range[0,50]},Table[Length[Union[Mod[#,n]&/@p9]],{n,100}]] (* Harvey P. Dale, Apr 22 2012 *)
a[n_] := IntegerExponent[3*n, 9] + MultiplicativeOrder[9, n/3^IntegerExponent[n, 3]]; Array[a, 100] (* Amiram Eldar, Aug 25 2024 *)

Formula

a(n) = valuation(3*n, 9) + A007740(n). - Amiram Eldar, Aug 25 2024