A note on Browkin’s and Cao’s cancellation algorithm

Andrzej Tomski,

Maciej Zakarczemny


Kontynuujemy badania nad generalizacją algorytmu sitowego browkina i Cao, [a. Tomski, m. Zakarczemny, On some cancellation algorithms, nnTDm. 23, 2017, p. 101–114]. niech f będzie funkcją o wartościach w zbiorze liczb naturalnych, określoną na s s , ≥1. usuwamy dzielniki wszystkich możliwych wartości funkcji f, w punktach, w których suma współrzędnych nie przekracza n. najmniejszą niewykreśloną liczbę naturalną nazywamy dyskryminatorem Df(n). W artykule uogólniamy pojęcie dyskryminatora. Znajdujemy jawne wzory lub oszacowania na dyskryminator dla szerokiej klasy ciągów. 

In this paper, we follow our generalisation of the cancellation algorithm described in our previous paper [a. Tomski, m. Zakarczemny, On some cancellation algorithms, nnTDm. 23, 2017, p. 101–114]. for f being a natural-valued function defined on s s , ≥1 we remove the divisors of all possible values of f in the points in which the sum of coordinates is less than or equal to n. The least non-cancelled number is called the discriminator Df(n). We find formulas, or at least an estimation for this discriminator, in the case of a broad class of sequences. 

Słowa kluczowe: dyskryminator, ciąg, kongruencja, liczby wstrętne, ciąg Thue-Morse’a , discriminator, sequence, congruence, odious numbers, Thue-Morse sequence

[1] Arnold L.K., Benkoski S.J., McCabe B.J., The discriminator
(a simple application of Bertrand's postulate), Amer. Math. Monthly,
92, 1985, 275-277.

[2] Bremser P. S., Schumer P.D., Washington L.C., A note on the incon-
gruence of consecutive integers to a fixed power, J. Number Theory
35, no. 1, 1990, 105-108.

[3] Browkin J., Cao H-Q., Modifications of the Eratosthenes sieve, Colloq.
Math., 135, 2014, 127-138.

[4] Haque S., Shallit J., Discriminators and k-regular sequences, IN-
TEGERS, 16, 2016, Paper A76.

[5] Moree P., Mullen G.L., Dickson polynomial discriminators,
J. Number Theory, 59, 1996, 88-105.

[6] Moree P., The incongruence of consecutive values of polynomials, Finite
Fields Appl., 2, 1996, 321-335.

[7] Moree P., Zumalacarregui A., Sălăjan's conjecture on dis-
criminating terms in an exponential sequence, J. Number Theory,
160, 2016, 646-665.

[8] Sierpiński W., Elementary theory of numbers, Warszawa 1964.

[9] Sierpiński W., Sur certaines hypothèses concernant les nombres premiers, Acta
Arith., 4, no.1, 1958, 20-30.

[10] Zhi-Wei Sun, On functions taking only prime values, J. Number Theory,
133, 2013, 2794-2812.

[11] Tomski A., Zakarczemny M., On some cancellation algorithms,
NNTDM, 23, 2017, 101-114.

[12] Zakarczemny M., On some cancellation algorithms, II, Technical Transactions, vol. 5/2017.

[13] Zieve M., A note on the discriminator, J. Number Theory, 73, 1998,

[14] Sloane N.J., The On-Line Encyclopedia of Integer Sequences,
available online at http://oeis.org (access: 05.10.2018).

[15] Ciolan A., Moree P., Browkin’s Discriminator Conjecture, 2017,
available online at https://arxiv.org/abs/1707.02183 (access: 05.10.2018).

[16] Melfi G., On the conditional infiniteness of primitive weird numbers,
J. Number Theory, 147, 2015, 508-514.

[17] http://webspace.ship.edu/msrenault/fibonacci/fib.htm (access: 05.10.2018).
http://www.mathpages.com/ home/kmath078/kmath078.htm (access: 05.10.2018).

[18] Baker R.C., Harman G., Pintz J., The difference between consecutive primes, II, Proc. Lond. Math Soc., 83, 2001, 532-562.
[19] Oppermann L., Om vor Kundskab om Primtallenes Moengde mellem givne Groenser, Overs. Dansk. Vidensk. Selsk. Forh., 1882, 169-179.

[20] H. Cramer, On the order of the magnitude of the difference between consecutive prime number, Acta Arith. 2, 1936, 23-46.