Showing posts with label doublet. Show all posts
Showing posts with label doublet. Show all posts

Thursday, 2 May 2024

Divisibility Sequences

It's easy to miss. The square numbers are 1, 4, 9, 16, 25, 36, 49 and so on but it's not obvious that the consecutive integers 27423, 27424 and 27425 are divisible by consecutive square numbers. Thus we have:$$ \begin{align} 27423 &= 3^2 \cdot 11 \cdot 277 \text{ divisible by }9=3^2\\27424 &= 2^5 \cdot 857 \text{ divisible by }16=4^2\\27425 &= 5^2 \cdot 1097 \text{ divisible by }25=5^2 \end{align}$$I only noticed this fact because my diurnal age today is 27423 and this number is a member of OEIS A178919:


 A178919

Smallest of three consecutive integers divisible respectively by three consecutive squares greater than 1.



Membership of this sequence does not come easy and can be seen in the list of its initial members (permalink):

2223, 5823, 9423, 13023, 16623, 20223, 23823, 27423, 31023, 32975, 34623, 38223, 41823, 45423, 49023, 52623, 56223, 59823, 63423, 67023, 70623, 74223, 77075, 77823, 81423, 85023, 88623, 92223, 95823, 99423, 103023, 106623, 110223

Not surprisingly membership in the equivalent sequence of two consecutive integers divisible by two consecutive squares is a lot easier. This sequence is OEIS A178918. The natural question to ask is whether there are groups of four consecutive integers divisible by four consecutive squares. Testing up in the range up to ten million, we find no such groups. However, they may well exist further out.

What about cubes? Can we find groups of three consecutive integers that are divisible by three consecutive cubes greater than 1. Indeed we can and, up one million, the sequence of the smallest members of these trios is (permalink):

106623, 322623, 538623, 754623, 970623 (not listed in the OEIS)

Let's look at the first member of the sequence where we find:$$\begin{align} 106623 &= 3^3 \cdot 11 \cdot 359 \text{ divisible by } 27 =3^3\\106624 &= 2^7 \cdot 7^2 \cdot 17 \text{ divisible by }64 =4^3\\106625 &= 5^3 \cdot 853 \text{ divisible by }125 =5^3 \end{align}$$What's interesting about sequences like this is that the numbers derive their membership via the groups to which they belong. For convenience, as in the case of OEIS A178919, only the first number in the group is listed. It is the relationship between the numbers in the group that are important. In the case of OEIS A178919 the numbers form a group of three that are consecutive and divisible by consecutive squares. Thus we have in the case of 27423:$$ \text{consecutive integers -->}\\ \frac{27423}{9} \, \frac{27424}{16} \, \frac{27425}{25} \\ \text{consecutive squares -->} $$or in the case of 106623:$$ \text{consecutive integers -->}\\ \frac{106623}{27} \, \frac{106624}{64} \, \frac{106625}{125} \\ \text{consecutive cubes -->} $$It would be interesting to explore divisibility using criteria other than divisibility by consecutive squares or cubes. What about divisibility of three consecutive integers by three consecutive fibonacci numbers (0, 1, 1, 2, 3, 5, 8, ...)? Well, if we ignore 0 and 1 and start with 2, it turns out that a great many groups of three qualify, most of which are divisible by 2, 3 and 5. The first of these begins with 8:$$ \begin{align} 8 &= 2^3 \text{ divisible by fibonacci number }2\\9 &= 3^2 \text{ divisible by fibonacci number } 3\\10 &= 2 \cdot 5 \text{ divisible by fibonacci number } 5 \end{align}$$There are 4417 such groups of three in the range up to 100,000, so they are very common. If we exclude 2, 3 and 5 and begin instead with 8, then the groupings of three become far less common (only 60 in the range up 100,000). The first of these begins with 376 (permalink):$$ \begin{align} 376 &= 2^3 \cdot 47 \text{ divisible by fibonacci number } 8\\377 &= 13 \cdot 29 \text{ divisible by fibonacci number }13\\378 &= 2 \cdot 3^3 \cdot 7 \text{ divisible by fibonacci number } 21 \end{align}$$This is clearly a topic worthy of further research.

Thursday, 24 March 2022

Doublets, Triplets etc.

One of the many properties associated with my diurnal age today of 26553 is that it's a member of OEIS A116057


  A116057

\(n\) times \( \Pi(n) \) is made of nontrivial runs of identical digits, where \( \Pi(n) \) is the prime counting function that returns the number of primes less than or equal to a given number.


It took me a little thought to get an algorithm that would return the members of this sequence but eventually I succeeded. While it may not be the most elegant of algorithms, it does get the job done. I've embedded the code from SageMathCell (permalink) below:


As can be seen the initial members of the sequence, up to 40,000, are:

[11, 37, 66, 154, 332, 750, 1696, 4000, 13684, 22308, 26640, 26653, 30327]

Taking the last member of the sequence, it can be seen that:$$ 30377 \times { \Large \Pi } (30327) =99442233 $$The algorithm is easily modifiable and below it is used to generate the initial terms of OEIS A033023:


 A033023

Numbers whose base-10 expansion has no run of digits with length < 2.     



Here the members of sequence, up to 40,000, are:

[11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, 444, 555, 666, 777, 888, 999, 1100, 1111, 1122, 1133, 1144, 1155, 1166, 1177, 1188, 1199, 2200, 2211, 2222, 2233, 2244, 2255, 2266, 2277, 2288, 2299, 3300, 3311, 3322, 3333, 3344, 3355, 3366, 3377, 3388, 3399, 4400, 4411, 4422, 4433, 4444, 4455, 4466, 4477, 4488, 4499, 5500, 5511, 5522, 5533, 5544, 5555, 5566, 5577, 5588, 5599, 6600, 6611, 6622, 6633, 6644, 6655, 6666, 6677, 6688, 6699, 7700, 7711, 7722, 7733, 7744, 7755, 7766, 7777, 7788, 7799, 8800, 8811, 8822, 8833, 8844, 8855, 8866, 8877, 8888, 8899, 9900, 9911, 9922, 9933, 9944, 9955, 9966, 9977, 9988, 9999, 11000, 11100, 11111, 11122, 11133, 11144, 11155, 11166, 11177, 11188, 11199, 11222, 11333, 11444, 11555, 11666, 11777, 11888, 11999, 22000, 22111, 22200, 22211, 22222, 22233, 22244, 22255, 22266, 22277, 22288, 22299, 22333, 22444, 22555, 22666, 22777, 22888, 22999, 33000, 33111, 33222, 33300, 33311, 33322, 33333, 33344, 33355, 33366, 33377, 33388, 33399, 33444, 33555, 33666, 33777, 33888, 33999]

Of course, the algorithm is easily modifiable to find numbers whose base-\(n\) expansion has no run of digits with length < 2. Here \(n \) can range from 2 to 36. For example, if \(n\)=16, then the numbers up to 40,000 that satisfy are:

[17, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255, 273, 546, 819, 1092, 1365, 1638, 1911, 2184, 2457, 2730, 3003, 3276, 3549, 3822, 4095, 4352, 4369, 4386, 4403, 4420, 4437, 4454, 4471, 4488, 4505, 4522, 4539, 4556, 4573, 4590, 4607, 8704, 8721, 8738, 8755, 8772, 8789, 8806, 8823, 8840, 8857, 8874, 8891, 8908, 8925, 8942, 8959, 13056, 13073, 13090, 13107, 13124, 13141, 13158, 13175, 13192, 13209, 13226, 13243, 13260, 13277, 13294, 13311, 17408, 17425, 17442, 17459, 17476, 17493, 17510, 17527, 17544, 17561, 17578, 17595, 17612, 17629, 17646, 17663, 21760, 21777, 21794, 21811, 21828, 21845, 21862, 21879, 21896, 21913, 21930, 21947, 21964, 21981, 21998, 22015, 26112, 26129, 26146, 26163, 26180, 26197, 26214, 26231, 26248, 26265, 26282, 26299, 26316, 26333, 26350, 26367, 30464, 30481, 30498, 30515, 30532, 30549, 30566, 30583, 30600, 30617, 30634, 30651, 30668, 30685, 30702, 30719, 34816, 34833, 34850, 34867, 34884, 34901, 34918, 34935, 34952, 34969, 34986, 35003, 35020, 35037, 35054, 35071, 39168, 39185, 39202, 39219, 39236, 39253, 39270, 39287, 39304, 39321, 39338, 39355, 39372, 39389, 39406, 39423]

In the OEIS, this is sequence A033029:


 A033029

Numbers whose base-16 expansion has no run of digits with length < 2.    


Here is a permalink to the algorithm. For example, take 26316 from this list as an example. We have \(26316_{{\small 10}}=66\text{cc}_{ {\small 16}}\).

The algorithm can be used to find some numbers with interesting properties. For example, in the range up to one million, what members of OEIS A033023 (sequence listed earlier) have a totient that is also a member of OEIS A033023? I won't embed the code but here is a permalink to the algorithm that I used to find the numbers with the required property. It turns out that there are only three:
  • \( \phi(9922)=4400\)
  • \( \phi(662233)=554400\)
  • \( \phi(990022)=449900\)

Tuesday, 12 March 2019

Euler's Totient Function

From Wikipedia:
Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function.
Today I turned 25545 days old and one of the points of interest about this number is that it forms a pair with 25546, both having the property that their totient values are the same (12480). The first member of the pairs of numbers with this property up to and including 25545 is given by OEIS A001274: numbers \(n\) such that \( \phi(n) = \phi(n+1) \):
1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545
Note that for all prime numbers \(p\), \( \phi(p)=p-1 \). These totient values (totatives) represent the maximum possible for numbers up to \(p\) and their points lie on the maximal line as shown in Figure 1:


Figure 1: generated using SageMathCell using
plot(lambda x:euler_phi(int(x)), (x,1,100))

From Figure 1 it can be seen that the totient values (totatives) for 1 and 2, 3 and 4, 15 and 16 are the same. Note that 5186 and 5187 themselves form a pair, meaning that the totient values of 5186, 5187 and 5188 are the same (2592). This is the only triplet that occurs for numbers up to \( 10^{13} \).

Euler's totient function is a multiplicative function, meaning that if two numbers \(m\) and \(n\) are relatively prime, then \( \phi(m \times n) = \phi(m) \times \phi(n) \). This is important in developing Euler's product formula along with the fact that: $$\phi(p^k)=p^{k-1} \bigg (1-\frac{1}{p} \bigg )$$The product formula is: $$\phi(n)=n \prod_{p|n} \bigg (1-\frac{1}{p} \bigg )$$Applying this to today's number 25545=3 * 5 * 13 * 131, we note that:$$ \phi(25545) = 25545\bigg (1-\frac{1}{3} \bigg ) \bigg (1-\frac{1}{5} \bigg ) \bigg (1-\frac{1}{13} \bigg ) \bigg (1-\frac{1}{131} \bigg )=12480$$