src/HOL/Number_Theory/Eratosthenes.thy
changeset 60583 a645a0e6d790
parent 60527 eb431a5651fe
child 61166 5976fe402824
equal deleted inserted replaced
60582:d694f217ee41 60583:a645a0e6d790
   117   show ?thesis
   117   show ?thesis
   118     by (auto simp add: mark_out_def mark_out_aux_def in_set_enumerate_eq intro: aux)
   118     by (auto simp add: mark_out_def mark_out_aux_def in_set_enumerate_eq intro: aux)
   119 qed
   119 qed
   120 
   120 
   121 lemma mark_out_aux_simps [simp, code]:
   121 lemma mark_out_aux_simps [simp, code]:
   122   "mark_out_aux n m [] = []" (is ?thesis1)
   122   "mark_out_aux n m [] = []"
   123   "mark_out_aux n 0 (b # bs) = False # mark_out_aux n n bs" (is ?thesis2)
   123   "mark_out_aux n 0 (b # bs) = False # mark_out_aux n n bs"
   124   "mark_out_aux n (Suc m) (b # bs) = b # mark_out_aux n m bs" (is ?thesis3)
   124   "mark_out_aux n (Suc m) (b # bs) = b # mark_out_aux n m bs"
   125 proof -
   125 proof goals
   126   show ?thesis1
   126   case 1
       
   127   show ?case
   127     by (simp add: mark_out_aux_def)
   128     by (simp add: mark_out_aux_def)
   128   show ?thesis2
   129 next
       
   130   case 2
       
   131   show ?case
   129     by (auto simp add: mark_out_code [symmetric] mark_out_aux_def mark_out_def
   132     by (auto simp add: mark_out_code [symmetric] mark_out_aux_def mark_out_def
   130       enumerate_Suc_eq in_set_enumerate_eq less_eq_dvd_minus)
   133       enumerate_Suc_eq in_set_enumerate_eq less_eq_dvd_minus)
       
   134 next
       
   135   case 3
   131   { def v \<equiv> "Suc m" and w \<equiv> "Suc n"
   136   { def v \<equiv> "Suc m" and w \<equiv> "Suc n"
   132     fix q
   137     fix q
   133     assume "m + n \<le> q"
   138     assume "m + n \<le> q"
   134     then obtain r where q: "q = m + n + r" by (auto simp add: le_iff_add)
   139     then obtain r where q: "q = m + n + r" by (auto simp add: le_iff_add)
   135     { fix u
   140     { fix u
   148       by (simp only: add_Suc [symmetric])
   153       by (simp only: add_Suc [symmetric])
   149     then have "Suc n dvd Suc (Suc (Suc (q + n) - Suc m mod Suc n)) \<longleftrightarrow>
   154     then have "Suc n dvd Suc (Suc (Suc (q + n) - Suc m mod Suc n)) \<longleftrightarrow>
   150       Suc n dvd Suc (Suc (q + n - m mod Suc n))"
   155       Suc n dvd Suc (Suc (q + n - m mod Suc n))"
   151       by (simp add: v_def w_def Suc_diff_le trans_le_add2)
   156       by (simp add: v_def w_def Suc_diff_le trans_le_add2)
   152   }
   157   }
   153   then show ?thesis3
   158   then show ?case
   154     by (auto simp add: mark_out_aux_def
   159     by (auto simp add: mark_out_aux_def
   155       enumerate_Suc_eq in_set_enumerate_eq not_less)
   160       enumerate_Suc_eq in_set_enumerate_eq not_less)
   156 qed
   161 qed
   157 
   162 
   158 
   163