Number-theoretic functions which are equivalent to number of divisors (Q1064776): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q405317 |
ReferenceBot (talk | contribs) Changed an Item |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Property / author | |||
| Property / author: Jeffrey O. Shallit / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0020-0190(85)90084-5 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2082542492 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4145769 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Approximate formulas for some functions of prime numbers / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A method for obtaining digital signatures and public-key cryptosystems / rank | |||
Normal rank | |||
Latest revision as of 18:15, 14 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Number-theoretic functions which are equivalent to number of divisors |
scientific article |
Statements
Number-theoretic functions which are equivalent to number of divisors (English)
0 references
1985
0 references
Let d(n) denote the number of positive integral divisors of n. In this paper we show that the Möbius function, \(\mu\) (N), can be computed by a single call to an oracle for d(n). We also show that any function that depends solely on the exponents in the prime factorization of N can be computed by at most \(\log_ 2N\) calls to an oracle for d(n).
0 references
Möbius function
0 references
oracle
0 references
prime factorization
0 references
