mersenneforum.org Divisibility by 7.
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2022-08-23, 23:14 #1 Charles Kusniec     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. Attached Thumbnails
 2022-08-24, 08:31 #2 xilman 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 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$
2022-08-24, 08:48   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5·1,319 Posts

Quote:
 Originally Posted by xilman (363 = 27 * 13).

2022-08-24, 12:07   #4
Charles Kusniec

Aug 2020
Guarujá - Brasil

1110112 Posts

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

Quote:
 Originally Posted by xilman 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

 2022-08-24, 13:54 #5 Dr Sardonicus     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 (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.
 2022-08-24, 14:11 #6 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 11001110000112 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.
2022-08-24, 15:31   #7
Charles Kusniec

Aug 2020
Guarujá - Brasil

738 Posts

Quote:
 Originally Posted by Dr Sardonicus 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

2022-08-24, 15:39   #8
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11,483 Posts

Quote:
 Originally Posted by Charles Kusniec I believe that you meant to say (364=28*13)..)
Corrrect. A silly tyop on my part.

2022-08-24, 15:42   #9
Charles Kusniec

Aug 2020
Guarujá - Brasil

59 Posts

Quote:
 Originally Posted by retina 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.

 2022-08-24, 16:01 #10 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 1071710 Posts This thread reminds me of my favourite Pete Conrad quote.
2022-08-24, 19:01   #11
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11,483 Posts

Quote:
 Originally Posted by Charles Kusniec 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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 3 2022-02-15 01:30 carpetpool carpetpool 1 2022-02-08 05:20 Charles Kusniec Number Theory Discussion Group 1 2021-06-04 14:08 jnml Miscellaneous Math 6 2020-05-02 12:41 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔