×

zbMATH — the first resource for mathematics

Formulas for the number of gridlines. (English) Zbl 1250.05023
Summary: Let \(l(n)\) be the number of lines through at least two points of an \(n \times n\) rectangular grid. We prove recursive and asymptotic formulas for it using respectively combinatorial and number theoretic methods. We also study the ratio \(l(n)/l(n-1)\). All this originates from Mustonen’s experimental results [Seppo Mustonen, “On lines and their intersection points in a rectangular grid of points,” http://www.survo.fi/papers/PointsInGrid.pdf].

MSC:
05A19 Combinatorial identities, bijective combinatorics
11B37 Recurrences
11N37 Asymptotic results on arithmetic functions
11P21 Lattice points in specified regions
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apostol T.M.: Introduction to Analytic Number Theory. Springer, Berlin (1976) Third printing, 1986 · Zbl 0335.10001
[2] Bender E.A., Patashnik O., Rumsey H. Jr: Pizza slicing, phi’s and the Riemann hypothesis. Am. Math. Mon. 101, 307–317 (1994) · Zbl 0814.11045 · doi:10.2307/2975623
[3] Codecà P.: A note on Euler’s $${\(\backslash\)phi}$$ -function. Ark. Mat. 19, 261–263 (1981) · Zbl 0481.10042 · doi:10.1007/BF02384483
[4] Mitrinović D.S., Sándor J., Crstici B.: Handbook of Number Theory. Kluwer, Dordrecht (1996)
[5] Mustonen, S.: On lines and their intersection points in a rectangular grid of points. http://www.survo.fi/papers/PointsInGrid.pdf
[6] Pétermann Y.-F.S.: On an estimate of Walfisz and Saltykov for an error term related to the Euler function. J. Théor. Nombr. Bordeaux 10, 203–236 (1998) · Zbl 0917.11047 · doi:10.5802/jtnb.225
[7] Saltykov, A.I.: On Euler’s function. [In Russian. Vestnik Moskov. Univ. Ser. I Mat. Meh. 6, 34–50 (1960)]
[8] Sheng T.K.: Lines determined by lattice points in R 2. Nanta Math. 10, 77–81 (1977) · Zbl 0367.52002
[9] Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/\(\sim\)njas/sequences/ · Zbl 1274.11001
[10] Suryanarayana D.: On the average order of the function $${E(x)=\(\backslash\)sum_{n\(\backslash\)le x} \(\backslash\)phi(n)-3x\^2/\(\backslash\)pi\^2}$$ II. J. Indian Math. Soc. (N.S.) 42, 195–197 (1978) · Zbl 0472.10045
[11] Suryanarayana D., Sitaramachandra Rao R.: On the average order of the function $${E(x)=\(\backslash\)sum_{n\(\backslash\)le x}\(\backslash\)phi(n)-3x\^2/\(\backslash\)pi\^2}$$ . Ark. Mat. 10, 99–106 (1972) · Zbl 0233.10026 · doi:10.1007/BF02384804
[12] Walfisz, A.: Weylsche Exponentialsummen in der neueren Zahlentheorie. VEB Deutsch. Verl. Wiss., Berlin (1963) · Zbl 0146.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.