mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Charles Kusniec

Reply
 
Thread Tools
Old 2022-08-23, 23:14   #1
Charles Kusniec
 
Charles Kusniec's Avatar
 
Aug 2020
Guarujรก - Brasil

59 Posts
Minus Divisibility by 7.

We learned in the video https://www.youtube.com/watch?v=UDQjn_-pDSs that to test whether a number N is divisible by 7 we can recursively apply the algorithm 5*(N mod 10)+floor(N/10).

Thus, all integers multiple of 7 that are not divisible by 7^2=49 will always arrive in the following repetitive sequence Axxxxxx=repeat{7, 35, 28, 42, 14, 21} as shown in the table C001116 below. This sequence Axxxxxx is 7 times https://oeis.org/A070365.



This loop follows the famous https://oeis.org/A020806 Period 6: repeat [1,4,2,8,5,7], as well as the https://oeis.org/A140430 Period 6: repeat [3, 2, 4, 1, 2, 0] and https://oeis.org/A070365 Period 6: repeat [1, 5, 4, 6, 2, 3].

Still during the application of the algorithm of the numbers that are divisible by 7 but are not divisible by 7^2=49, we find two more new sequences. Cxxxxxx = 7*n mod 10 = Period 6: repeat [7, 5, 8, 2, 4, 1] and Dxxxxxx = 5*(7*n mod 10) = Period 6: repeat [35, 25, 40, 10, 20, 5].

The application of the algorithm of the numbers that are divisible by 7 and divisible by 7^2=49, result in table C001117 below.



For completeness, it is worth studying the appearance of repetitive sequences when we apply the divisibility by 7 algorithm to the sequence https://oeis.org/A008589 of the multiples of 7. See table C001118 below.



It generates 2 new interesting sequences Gxxxxxx and Hxxxxxx to be studied.
Attached Thumbnails
Click image for larger version

Name:	C001116 Repetitive sequences generated by the divisibility algorithm of the numbers that are div.png
Views:	110
Size:	39.4 KB
ID:	27229   Click image for larger version

Name:	C001117 Repetitive sequences generated by the divisibility algorithm of the numbers that are div.png
Views:	112
Size:	27.5 KB
ID:	27230   Click image for larger version

Name:	C001118 Repetitive sequences generated by the divisibility by 7 algorithm over A008589 the multi.png
Views:	110
Size:	44.0 KB
ID:	27231  
Charles Kusniec is offline   Reply With Quote
Old 2022-08-24, 08:31   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11,483 Posts
Default

Much easier, in my view, is to test for 7, 11 and 13 simultaneously. Note that 7*11*13 = 1001, so apply the rule of 11 three digits at a time.

Here is a worked example on 784971746890695 (just some random typing on the keypad)

695 + 746 + 784 = 2225 and 890 + 971 = 1861 and 2225 - 1861 = 364.

The 3-digit number is now small enough for mental arithmetic. Clear it is a multiple of 7 (being 52 * 7) and it is only slightly harder to show that it is not divisible by 11 (it leaves remainder 1 because 363=11*33) but is divisible by 13 (363 = 27 * 13).

Just to check:

pcl@nut:~/Astro$ bc
bc 1.07.1
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
784971746890695 % 7
0
784971746890695 % 11
1
784971746890695 % 13
0

pcl@nut:~/Astro$
xilman is offline   Reply With Quote
Old 2022-08-24, 08:48   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5·1,319 Posts
Default

Quote:
Originally Posted by xilman View Post
(363 = 27 * 13).
retina is online now   Reply With Quote
Old 2022-08-24, 12:07   #4
Charles Kusniec
 
Charles Kusniec's Avatar
 
Aug 2020
Guarujรก - Brasil

1110112 Posts
Default

Quote:
Originally Posted by xilman View Post
but is divisible by 13 (363 = 27 * 13).
I believe that you meant to say (364=28*13).

Quote:
Originally Posted by xilman View Post
Much easier, in my view, is to test for 7, 11 and 13 simultaneously. Note that 7*11*13 = 1001, so apply the rule of 11 three digits at a time.
The idea of this post is to limit ourselves to the divisibility of 7. Only this way we can directly find the sequences that have bijection with the famous sequence https://oeis.org/A020806 Period 6: repeat [1,4,2,8,5,7].

So, I was surprised to find two final loops: (i) the sequence Axxxxx=repeat[7, 35, 28, 42, 14, 21] as an "oscillating" loop, and (ii) another "terminating" loop Exxxxxx=repeat[49]. The latter reminds us the "terminating" loop of Colatz's conjecture that it always ends in repeat[1].

That is, looking only at 7, we see that the recursive algorithm of divisibility of 7 has two final loops. Is this new?

Also, I forgot to mention in the original post that the sequence of unit digits in Axxxxx=repeat[7, 35, 28, 42, 14, 21] follows the famous sequence https://oeis.org/A020806 Period 6: repeat [1,4,2,8,5,7]. The sequence of the tens digit follows https://oeis.org/A134977 Period 6: repeat [1, 4, 2, 3, 0, 2].

(P.S.: when we do bijection we don't consider the offset between the sequences and neither the directions.)

Last fiddled with by Charles Kusniec on 2022-08-24 at 12:31
Charles Kusniec is offline   Reply With Quote
Old 2022-08-24, 13:54   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×11×181 Posts
Default

I note that if 10*k + r is divisible by 7, then so is k + 5*r.

However, it seems silly to compile, under the heading "Divisibility by 7," tables whose entries are already known to be divisible by 7.

I note that if 10*k + r is not divisible by 7, then k + 5*r may have a different (non-zero) remainder modulo 7.

I also note that it is possible to have 5*r + k > 10*k + r when k is a non-negative integer and 0 โ‰ค r โ‰ค 9. The transformation never reduces a number by more than a factor of 10.

The usual tests for divisibility by 7 replace 10^k in the 10^k place of the decimal representation by something congruent to 10^k (mod 7), so preserve the remainder mod 7.

xilman has already given an example replacing 1, 10, 10^2, 10^3, 10^4, 10^5, .. with 1, 10, 10^2, -1, -10, -10^2, ... This preserves remainders modulo 1001.

As a script-writing exercise I decided to sic the mighty Pari-GP on the problem of iterating the transform 10*k + r -> k + 5*r starting with 1. Note that 10 = 10*1 + 0 transforms to 1 + 5*0 = 1.

Code:
? v=[1];n=1;until(n==10,w=divrem(n,10);n=[1,5]*w;v=concat(v,[n]));print(v)
[1, 5, 25, 27, 37, 38, 43, 19, 46, 34, 23, 17, 36, 33, 18, 41, 9, 45, 29, 47, 39, 48, 44, 24, 22, 12, 11, 6, 30, 3, 15, 26, 32, 13, 16, 31, 8, 40, 4, 20, 2, 10]
? print(#v)
42
The entries of v are the positive integers less than 49 which are not divisible by 7.
Dr Sardonicus is offline   Reply With Quote
Old 2022-08-24, 14:11   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11001110000112 Posts
Default

I'm not sure why people use these "tricks". They are more complicated and slower than simply passing though the number one digit at a time with normal long division and deriving the remainder.

I can do ~4 digits/second. I'm sure others can do it even faster.
retina is online now   Reply With Quote
Old 2022-08-24, 15:31   #7
Charles Kusniec
 
Charles Kusniec's Avatar
 
Aug 2020
Guarujรก - Brasil

738 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
However, it seems silly to compile, under the heading "Divisibility by 7," tables whose entries are already known to be divisible by 7.
To me, it seems silly to compile, under the heading "Divisibility by 7," a script whose entries are already known NOT to be divisible by 7.

While the entries of numbers less than 49 divisible by 7 are only half a dozen, for you to compile your script you had to enter 3.5 dozen numbers less than 49 not divisible by 7.

See in the figures bellow what happens in the algorithm of my tables for 13!, 14! and (13!+1).

13! divided by 7, the loop is Axxxxxx=repeat[7, 35, 28, 42, 14, 21] = 7 * https://oeis.org/A070365. All sum/7 are integer.


14! divided by 7, the loop is Exxxxxx=repeat[49]. all sum/7 are integer.


And (1+13!) a non divisible by 7, does not have loop or there is no sum/7 integer:
Attached Thumbnails
Click image for larger version

Name:	factorial of 13.png
Views:	83
Size:	10.4 KB
ID:	27232   Click image for larger version

Name:	factorial of 14.png
Views:	83
Size:	9.1 KB
ID:	27233   Click image for larger version

Name:	1 plus factorial of 13.png
Views:	83
Size:	14.4 KB
ID:	27234  
Charles Kusniec is offline   Reply With Quote
Old 2022-08-24, 15:39   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11,483 Posts
Default

Quote:
Originally Posted by Charles Kusniec View Post
I believe that you meant to say (364=28*13)..)
Corrrect. A silly tyop on my part.
xilman is offline   Reply With Quote
Old 2022-08-24, 15:42   #9
Charles Kusniec
 
Charles Kusniec's Avatar
 
Aug 2020
Guarujรก - Brasil

59 Posts
Default

Quote:
Originally Posted by retina View Post
I'm not sure why people use these "tricks". They are more complicated and slower than simply passing though the number one digit at a time with normal long division and deriving the remainder.
Here the idea is still to understand the divisibility algorithms so that we can apply them to other recursive sequences.

Obviously, the good idea of xilman can be more comprehensive, but as I said before, these tables show us new sequences that have bijection with the famous sequence https://oeis.org/A020806 Period 6: repeat [1,4,2,8,5,7]. Now, this is the objective.
Charles Kusniec is offline   Reply With Quote
Old 2022-08-24, 16:01   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101ร—103 Posts

1071710 Posts
Default

This thread reminds me of my favourite Pete Conrad quote.
Uncwilly is offline   Reply With Quote
Old 2022-08-24, 19:01   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11,483 Posts
Default

Quote:
Originally Posted by Charles Kusniec View Post
Obviously, the good idea of xilman can be more comprehensive.
Not my good idea. The algorithm has been known for a very long time.I wouldn't be surprised to learn that Fermat used it.
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
more on divisibility of n^2+n+41 where n is a positive integer. MattcAnderson MattcAnderson 3 2022-02-15 01:30
Sieve for divisibility sequences carpetpool carpetpool 1 2022-02-08 05:20
Divisibility between polynomial expressions Charles Kusniec Number Theory Discussion Group 1 2021-06-04 14:08
Divisibility function jnml Miscellaneous Math 6 2020-05-02 12:41
A great universal divisibility rule JM Montolio A Miscellaneous Math 3 2018-02-27 16:11

All times are UTC. The time now is 02:40.


Sun Sep 25 02:40:10 UTC 2022 up 38 days, 8 mins, 0 users, load averages: 1.22, 1.28, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”