20220823, 23:14  #1 
Aug 2020
Guarujรก  Brasil
59 Posts 
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. 
20220824, 08:31  #2 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11,483 Posts 
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 3digit 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 19911994, 1997, 1998, 2000, 2004, 2006, 2008, 20122017 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$ 
20220824, 08:48  #3 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5·1,319 Posts 

20220824, 12:07  #4  
Aug 2020
Guarujรก  Brasil
111011_{2} Posts 
I believe that you meant to say (364=28*13).
Quote:
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 20220824 at 12:31 

20220824, 13:54  #5 
Feb 2017
Nowhere
3×11×181 Posts 
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 (nonzero) remainder modulo 7. I also note that it is possible to have 5*r + k > 10*k + r when k is a nonnegative 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 scriptwriting exercise I decided to sic the mighty PariGP 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 
20220824, 14:11  #6 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1100111000011_{2} Posts 
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. 
20220824, 15:31  #7  
Aug 2020
Guarujรก  Brasil
73_{8} Posts 
Quote:
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: 

20220824, 15:39  #8 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11,483 Posts 

20220824, 15:42  #9  
Aug 2020
Guarujรก  Brasil
59 Posts 
Quote:
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. 

20220824, 19:01  #11 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11,483 Posts 

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  20220215 01:30 
Sieve for divisibility sequences  carpetpool  carpetpool  1  20220208 05:20 
Divisibility between polynomial expressions  Charles Kusniec  Number Theory Discussion Group  1  20210604 14:08 
Divisibility function  jnml  Miscellaneous Math  6  20200502 12:41 
A great universal divisibility rule  JM Montolio A  Miscellaneous Math  3  20180227 16:11 